perm filename NOTES.JRA[LSP,JRA]10 blob
sn#166657 filedate 1974-12-03 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00046 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 .SEC(Evaluation of LISP expressions,Evaluation)
C00023 00003 .SS(Sexpr translation of LISP expressions)
C00030 00004 .SS(A first look at symbol tables,symbol tables,P92:)
C00038 00005 .SS(Introduction to %3λ%*-expressions)
C00043 00006 .SS(%3λ%*-expressions,%3λ%*-expressions,P49:)
C00071 00007 .SS(Mechanization of evaluation,,P6:)
C00084 00008 .SS(Examples of %3eval%*,examples of %3eval%*)
C00088 00009 It should now be clear that %3eval%* and friends %2do%* begin to
C00093 00010 .<<the | | symbol table >>
C00104 00011 .SS(Environments and bindings,,P77:)
C00114 00012 .REQUIRE "PROB8.PUB" SOURCE_FILE
C00115 00013 .SS(%3label%*,%3label%*,P38:)
C00120 00014 .SS(Functional Arguments and Functional Values,functional argument,P76:)
C00135 00015 .<<pic of funarg execution>>
C00144 00016 .SS(special forms,special form,P8:)
C00151 00017 .SS(The %3prog%*-feature,,P37:)
C00165 00018 Now that assignment statements are out in the open let's reexamine "<=".
C00167 00019 .SS(In retrospect,,P90:)
C00184 00020 .SS(Towards a Mathematical Semantics,,P85:)
C00197 00021 Let us begin to relate these intuitions to our discussion of
C00206 00022 Then, for example, the
C00220 00023 To describe the evaluation of a function-call in LISP we must add
C00225 00024 This will suffice for our current λ-definitions we need not modify %dl%*
C00246 00025 .SEC(Running on the machine)
C00252 00026 .SS(%3evalquote%*,%3evalquote%*)
C00260 00027 .SS(A project: extensions to %3eval%*,%3eval%*,P67:)
C00269 00028 .SS(A project: Syntax-directed processes,syntax-directed)
C00270 00029 .SEC(Implementation of the Static structure of LISP,static structure)
C00276 00030 .SS(AMBIT/G,AMBIT/G,P26:)
C00287 00031 .SS(Symbol tables: revisited)
C00302 00032 .<<atom struct for fact>>
C00313 00033 .<<pic of NIL>>
C00314 00034 .SS(A first look at %3cons%1)
C00324 00035 .CENT(A simple LISP garbage collector written in LISP)
C00339 00036 .CENT(Problems)
C00341 00037 .SS(%3read%* and %3print%*,,P13:)
C00348 00038 .SS(Hashing,hashing,P14:)
C00355 00039 .SS(A review of the structure of the LISP machine,LISP machine)
C00357 00040 .SS(Binding revisited,bind,P78:)
C00390 00041 .SS(Macros and special forms,macros,P18:)
C00426 00042 .SS(%aSM%*-%3eval%*,%3eval%*,P30:)
C00432 00043 .CENT(Problems)
C00444 00044 .SS(An alternative: deep bindings,deep binding)
C00464 00045 .SS(Epilogue)
C00468 00046 .END "JRA"
C00469 ENDMK
C⊗;
.SEC(Evaluation of LISP expressions,Evaluation)
.BEGIN indent 20,20;
"... I always worked with programming languages because it seemed to me
that until you could understand those, you really couldn't understand
computers. Understanding them doesn't really mean only being able to use
them. A lot of people can use them without understanding them. ..."
.END
.BEGIN TURN ON "→";
→Christopher Strachey, %3The Word Games of the Night Bird.%*
.END
.BEGIN "JRA" TURN ON "←","#";
.SS(Introduction)
%1
We shall now look more closely at the informal
process which we have been using in the ⊗→evaluation↔← of LISP expressions.
This is motivated by at least two desires.
First, we want to run our LISP programs on a machine.
Any attempted implementation of LISP must be grounded on a precise,
and clear understanding of what LISP-evaluation
entails. Indeed, a deep understanding
of evaluation is a prerequisite for implementation of any language.
The question of evaluation cannot be sidestepped by basing a language
on a compiler. A compiler must produce code which when executed, simulates
the evaluation process. There is no escape.
Our second reason for persuing evaluation involves the question
of programming language specification. This title covers a multitude
of sins.
At a practical level we would a clean, machine independent, "self-evident"
description of a language specification, so that the agony involved
in implementing the design can be minimized. At a more abstract level,
we should try to understand just what %2is%* specified when we design a
language. Are we specifying a single machine, a class of machines, a
class of mathematical functions; just what is a language?
The syntactic specification of languages is reasonably well established,
but syntax is only the tip of the iceberg. Our study of LISP
will address itself to the deeper problems of semantics, or meaning,
of languages.
How can be begin to understand evaluation? Again, mathematics is
the exemplar.
From our earliest grade school days we had to evaluate simple
arithmetic expressions. Later, in algebra we managed to cope with
expressions involving function application. Most of us survived the
experience. We should now try to understand the processes we used in these
simple arithmetic cases, doing our examination at the most mechanical
level.
Those parts which are not mechanical⊗↓Are machine-independent, if you
wish.←, should be remembered. We will make reasonable choices so that
the process %2does%* become mechanical, and proceed. Later, we should
reflect on what effect our choices had on the resulting scheme ⊗↓implementation←.
The first thing to note in examining simple arithmetic
examples is that %2nothing%* is really said about the process
of evaluation.
When asked to evaluate
%3(2*3)#+#(5*6)%* we never specify which summand is to be evaluated first.
Indeed it doesn't matter here. %36#+#(5*6)%* or %3(2*3)#+#30%* both
end up %336%*.
Does it %2ever%* matter? "+" and "*" are examples of arithmetic functions;
can we always leave
the order of evaluation unspecified for arithmetic functions?
How about evaluation of arbitrary functional expressions?
If the order doesn't matter, then the specification of the evaluation
process becomes much simpler. If it %2does%* matter then we must
know why and where.
.P98:
We have seen that the order of evaluation %2can%* make a difference in LISP.
On {yon(P106)} we saw that LISP's computational
interpretation of function evaluation require some care.
On {yon(P17)} we saw that order of
evaluation in conditional expressions can make a difference.
We must make %2some%* decision regarding
the order of evaluation of the arguments to a function call,
say %3f[t%41%*;t%42%*; ...t%4n%1]. We will assume that we will evaluate the arguments
from left to right.
Or consider the example due to J. Morris:
.P84:
.BEGIN CENTERIT;
←%3f[x;y] <= [x = 0 → 0; T → f[x-1;f[y-2;x]]]]%*.
.END
Evaluation of %3f[2;1]%*
will terminate if we always evaluate the leftmost-outermost occurrence of %3f%*.
Thus:
←%3f[2;1] = f[1;f[-1;2]] = f[0;f[f[-1;2]-2;-1] = 0;%*
However if we evaluate the rightmost-innermost occurrences first, the
computation will not terminate:
←%3f[2;1] = f[1;f[-1;2]] = f[1;f[-2;f[0;-1]]] = f[1;f[-2;0]] = ... .%*
So the choice of evaluation schemes is, indeed, fraught with peril.
The evaluation scheme which we choose
is called %2⊗→inside-out↔←%* or %2⊗→call-by-value↔←%*. Alternative proposals exist
and have their merits; ⊗→call-by-name↔← (outside-in) evaluation is another
well-known scheme.
From a computational
perspective, we can live with call-by-value. Though the use of such a rule
may lead to non-terminating computations when call-by-name would run to
completion, the efficient implementation available for call-by-value
usually outweighs any theoretical advantage possessed by the other leading
product.
Intuitively, call-by-value says:
evaluate the arguments to a function before you attempt to apply the arguments
to the function definition.
Let's look at a simple arithmetic example.
Let %3f[x;y]%* be %3x%82%*#+#y%1 and consider %3f[3+4;2*2]%*. Then
call-by-value says evaluate the arguments, getting %37%* and %34%*;
associate those values
with the formal parameters of %3f%* (i.e. %37%* with %3x%* and
%34%* with %3y%*) and then evaluate the body of
%3f%* resulting in #%37%82%*#+#4#=#57%1.
Call-by-name says pass the %2unevaluated%* actual
parameters to the function, giving %3(3+4)%82%*#+#2*2%1
which also evaluates to %357%*.
Call-by-name is essentially a "substitution followed by simplification"
system of computation. Implementations of this scheme involve
unacceptable inefficiencies.
We will say more about call-by-name and other styles of
evaluation later. Most of this section will be restricted to call-by-value.
Notice that the call-by-value interpretation we are advocating for arithmetic
expressions
is recursive. It goes something like this:
If the expression to be evaluated is a constant then the value
of the expression is that constant. (the value of %33%* is %33%*
⊗↓We are ignoring the distinction between the %2numeral%* %33%*
and the %2number%3 3.%1←).
If the expression is a variable then see what the current value associated
with that variable is. Within the evaluation of say
%3f[3;4]%* where %3f[x;y]#<=#x%82%*#+#y %1the current value of the variable
%3x%* is %33%*. The only other kind of arithmetic expression that we can have is a function
name followed by arguments, for example, %3f[3;4]%*.
In this case we first evaluate the arguments ⊗↓Here we are using the evaluation
process recursively.←;
and then apply the definition of the function to those
evaluated arguments. How do we apply the evaluated arguments to the function
definition? We associate or ⊗→bind↔← the formal parameters (or variables)
of the definition to the values of the actual parameters.
We then evaluate the body of the function in this new environment.
Notice that we do %2not%* explicitly substitute the values for the variables
which appear in an expression. We simulate substitutions by symbol-table lookup.
.P80:
A moments reflection on the informal evaluation process
we use in LISP should convince us of the plausibility of
describing LISP evaluation at a similar level of precision.
First, if the LISP expression is a constant, then the value of the
expression is that constant.
What are the constants of LISP? They're just the S-exprs.
Thus
the value of %3(A#.#B)%* is %3(A#.#B)%*; just like the value of %33%* is %33%*.
The additional artifact of LISP which we have to include in a discussion of
evaluation is the conditional expression. But clearly its evaluation can also
be precisely specified. We did so on {yon(P40)}.
So, in more specific detail, here is some of the structure of the
LISP evaluation mechanism:
If the expression to be evaluated is a constant then the value
is that constant.
If the expression is a variable find its value in the current environment.
If the expression is a conditional expression then it is of the form
%3[p%41%* → e%41%*; p%42%* → e%42%*; ... p%4n%* → e%4n%1]. Evaluate it
using the semantics defined on {yon(P40)}.
If the expression is of the form: function name followed by
arguments then:
.BEGIN INDENT 10,10,10;GROUP;
%21.%1 Evaluate the arguments (from left to right).
%22.%1 Find the definition of the function.
%23.%1 Associate the evaluated arguments with the formal parameters
in the function definition.
%24.%1 Evaluate the body of the function, while remembering the values
of the variables.
.END
So we %2can%* describe the outline of a mechanical procedure which
is used in the evaluation of LISP functions.
Now for the final step.
We have seen ({yonss(P2)}) that we can transcribe
the above simple kind of arithmetic evaluation to a recursive LISP program.
That program operates on a representation of the expression and
produces the value.
In the same vein, recall our discussion
of the differentiation formulas in {yonss(P41)}. We described the mechanism of
differentiating as a recursive process. Then mechanized that scheme
as a LISP function. We translating the polynomials to S-expr notation,
since the domain of LISP functions are S-exprs.
Having demonstrated an informal, but reasonable precise, evaluation scheme
for LISP,
our discussion of LISP is ready for a similar development.
It should be clear that we could write a LISP
function representing the evaluation process provided that we can
find a representation for LISP expressions as S-expressions.
This mapping of LISP expressions to S-exprs is our first order of business. We
will accomplish this mapping by using an extension of the scheme introduced in
{yonss(p41)}.
Once that's done we will have a LISP program which describes the
evaluation process used in LISP, just as {yonss(P2)} is a LISP
progam describing the evaluation process used in a class of
arithmetical expressions.
This whole process of mapping LISP expressions onto s-exprs, and writing a LISP
function to act as an evaluator may seem a bit incestuous or difficult to fathom.
First, it is no more obscure than the polynomial evaluation or
differentiation examples.
It is just another instance of the diagram of {yon(P46)},
only now we are applying the process to LISP itself. The effect is to force
us to make precise exactly what is meant by LISP evaluation. This
precision will have many important ramifications.
Second, we've been doing evaluation of s-expr representations of
LISP expressions already.
The %2great mother of all functions%* is exactly the evaluation mechanism for
the LISP primitive functions and predicates, %3car, cdr, cons, atom%* and %3eq%*
when restricted to functional composition and constant arguments.
The %2great mother revisited%* is the extension to conditional expressions.
But let's stop for some examples of translating LISP functions into Sexpr notation.
.SS(Sexpr translation of LISP expressions)
.BEGIN NOFILL;TABS 18,43;TURN ON "\";
.GROUP
\%2LISP expression\translation as Sexpr
%1we will represent numbers just as numbers, e.g.:
\%32\2
%1we will translate identifiers to their upper-case counterpart. Thus:
%3\x\X
\y2\Y2
\car\CAR
.APART
.BEGIN FILL;
%1Now we've got a problem:
We wish to map arbitrary LISP expressions to Sexpressions. The LISP expression
%3x%* translates to %3X%*; %3X%* is itself a LISP expression (a constant);
%2it%* must also have a translate.
We must be a little careful here.
When we write Son of Great Mother we will give it an sexpr representation
of a form to be evaluated. We might give it the representation of %3car[x]%*
in which case the value computed will depend on the current value bound to %3x%*.
We might also give the representation of %3car[X]%*; in this case we should
expect to be presented with an error message.
Or, for example some function %3foo%* we wish to write may return the sexpr
representation of a LISP form as its value.
Say %3foo[1]%* returns the representation of %3car[x]%* and %3foo[2]%* returns
the representation of %3car[X]%*. We must be able to distinguish between these
representations.
That is, given the representation,
there should be exactly one way of interpreting it as a LISP expression.
The mapping must be 1-1. So we must represent %3x%* and %3X%* as %2different%* sexprs.
The translation scheme we pick is:
for any sexpression, y, its translation is %3(⊗→%3QUOTE%*↔←%1 y%3)%1.
.END
.GROUP
.SELECT 1;
For example:
\%3X\(QUOTE X)
\(A . B)\(QUOTE (A . B))
\QUOTE\(QUOTE QUOTE)
.APART
.GROUP
%1
.BEGIN FILL;
We must also show how to map expressions of the form %3f[e%41%*#;#...#;e%4n%*]%1
onto sexprs.
We have already seen one satisfactory mapping for functions in prefix form
in {yonss(P41)}.
We will use that mapping (called Cambridge Polish) here. That is:
.END
\%3f[e%41%*;e%42%*; ...e%4n%*]\(F e%41%*' e%42%*' ...e%4n%1')
\\ where %3e%4i%1' is the translate of %3e%4i%3
%1Examples:%*
\car[x]\(CAR X)
\car[X]\(CAR (QUOTE X))
\cons[cdr[(A . B)];x]\(CONS (CDR (QUOTE (A . B))) X)
.APART
.GROUP
%1What's left? conditional expressions. The mapping is self-explanatory.
\%3[p%41%* → e%41%*; ... p%4n%* → e%4n%*]\(⊗→%3COND%*↔← (p%41%*' e%41%*') ... (p%4n%*' e%4n%*'))
%1and an example:%3
\[atom[x] →1; q[y] → X]\(COND ((ATOM X) 1) ((Q Y) (QUOTE X)))
%1
.APART
.END
.P44:
Notice that %3(COND#(#...#))%* and %3(QUOTE#...#)%* %2look%* like translates of function
calls of the form %3cond[#...#] %* and %3quote[#...#]%*. This is %2not%* the case;
%3QUOTE%* and %3COND%* are not translates of LISP functions.
The constructs %3QUOTE%* and %3COND%* do not use call-by-value evaluation and
are handled in a special way as we shall soon see.
Since %3T%* and %3NIL%* are used so frequently, we chose their
translates to be %3T%* and %3NIL%* rather than %3(QUOTE#T)%* and %3(QUOTE#NIL)%*.
You should now go back and look at the %3tgm%*'s ({yonss(P39)}) again now
that you know
what they mean. You should note that, for atoms, the great
mothers are only defined for %3T%* and %3NIL%*. Other atoms (which are
the translates of variables) are not recognized and return a h.s.⊗↓habitually
saccharine.← message.
The question of variables requires some careful study. Before we do that,
let's see what the great mothers actually accomplish.
First, %3tgm%*'s explicitly tell you what the meaning of various subsets
of LISP is. That is, the %3tgm%*'s explicitly codify the semantics (or meaning)
of LISP. Next, if you are able to code %3tgm%* on a machine, then you can
input the S-expr form of LISP expressions and they will be evaluated for you.
%2Great mother does it all.%*
The part of our informal argument which is clearly missing
in the %3tgm%*'s is the details of handling variables and the names of functions. That is,
how do we describe the binding of variables to values as a mechanical process?
And given the name of a defined function, how do we retrieve the actual definition?
These are actually the same problem: that of symbol table manipulation.
.SS(A first look at symbol tables,symbol tables,P92:)
%1
One of the distinguishing features of Computer Science is
its reliance on the ability to store and recover information.
Any formalism which purports to address itself to Computer Science
must take this into account. In particular we must be able to
handle the effect of assignment or binding, that is, the association
of a value with a name in an environment. A common device used to accomplish this
is a symbol table. In essence, a symbol table is simply a set of ordered pairs
of objects (a function or relation, if you wish). One of the
elements of each pair is a name; the other is its value.
As an abstract operation, finding an element in a symbol table is
quite simple. Given a set of ordered pairs and an variable,
find a pair with first element the same as the given variable.
This level of abstractions is a bit too spartan.
The level of abstraction wish we envision looks on a
symbol table as a %2sequence%* of pairs, each pair representing a variable
and its corresponding value.
The addition of sequencing seems minor, but its importance will become
apparent.
We will use the list-operations for examining elements of the sequence,
but we will need to designate a selector, %3name%*, to locate
the name-component of a pair; and a selector, %3value%*, to
retrieve the value component.
These simple symbol tables are also known as ⊗→association lists↔←
or %2⊗→a-lists↔←%*.
Thus %3assoc%* will be the name of our function to search a symbol table.
%3assoc%* will take two arguments: a name and a symbol table.
It will examine the table from left to right, looking for the first
pair whose %3name%*-part matches the given name. If such a pair is found,
then that pair is returned. If %2no%* such pair is found, the
result is undefined.
.BEGIN TABS 10,25;TURN ON "\";NOFILL;
.SELECT 3;
\assoc[x;l] <= \[\ eq[name[first[l]];x] → first[l];
\\ T → assoc[x;rest[l]]]
.END
Notice there may be more than one pair with the same
%3name%*-part; only the %2first%* is found.
The ordering inherent in the searching algorithm will be utilized
very soon.
We will come back to symbol tables in a while to study
the problems of efficient storage and retrieval of information.
It will suffice now simply to think of a symbol table as represented
in LISP by a list of dotted pairs, a name dotted with value.
In this representation, then, %3name[x] <= car[x]%*, and %3value[x]#<=#cdr[x]%*.
For completeness, we should also specify a constructor. Though we
won't need it for a while, it's name is ⊗→%3mkent%*↔←, and
will take a name and a value and return a new entry. Its representation here is
%3mkent[x;y]#<=#cons[x;y]%*.
.GROUP
.P110:
Recall that we are representing variables as atoms; then if %3x, y, %*and %3z%*
had current values %32, 3, %*and %34%*, then a symbol table describing that fact could
be encoded as:
←%3((X . 2)(Y . 3)(Z . 4)) .%1
.APART
.GROUP
.BEGIN CENTERIT;GROUP;
%1For example:
←%3assoc[Y;((X . 2)(Y . 3)(Z . 4))] = (Y . 3)
←assoc[U;((X . 2)(Y . 3)(Z . 4))] %1 is undefined.
.END
.APART
%1
How are we to represent bindings of variables to non numeric S-exprs? For example,
how will we represent: "the current value of %3x%* is %3A%*"?
We will place the dotted-pair %3(X . A)%* in the table. Now this
representation is certainly open to question: why not add
%3(X .(QUOTE A))%*? The latter notation is more consistent
with our conception of representation espoused on {yon(P46)}.
That is, we map LISP expressions to Sexpressions; perform the
calculations on this representation, and finally %2reinterpret%*
the result of this calculation as a LISP expression. The representation
we have chosen for symbol tables obviates the last reinterpretation
step. Now it will turn out that for our initial subsets of LISP
this reinterpretation step simple would involve "stripping" the %3QUOTE%*s.
The only "values" which a computation can return are constants; later
things will become more difficult. Perhaps this representation of
table entries is a poor one, we will see.
In studying any existing language, or contemplating the design of
any new one, we must question each detail of representation. Decisions
made too early can have serious consequences.
However, in defense of LISP, it must be remembered that
LISP was conceived at the time that FORTRAN was believed to be a
gift from God. Only later did we learn the true identity of the donor.
.SS(Introduction to %3λ%*-expressions)
How about adding things to tables? We will see that %3cons%* plus
the recursion mechanism will automatically update the symbol table
for %2Great-mother%* when we call a function.
We will be adding entries to the symbol table when we call a function,
binding the formal parameters to the actual parameters. Intuitively,
when we call %3f[x;y] <= (x*y + y) %1in%3 f[2;3]%1, the dotted pairs
%3(X . 2) %*and %3 (Y . 3)%* should find their way into the table.
Besides the binding of formal parameters to actual values, there is
another binding process occurring in LISP.
Before we can call the function named %3f%*, its definition must
be in the symbol table; so there should be an entry (dotted pair)
with name-part %3F%* and a value-part representing %3(x*y + y)%*. An obvious
representation is perhaps,
←%3(PLUS (TIMES X Y)Y)%*
That's not quite good enough. If we simply associate the name %3F%*
with the list %3(PLUS#(TIMES#X#Y)#Y)%*, we will have lost some crucial information.
Namely, the relation between the variables %3x%* and %3y%* and the
body of the function will not be present. For example, %3f[y;x]#<=#(x*y#+y)%*
is %2not%*
the same function, but in our naive translation they have the same
representation. The solution is obvious: we must associate the list of
formal parameters with the body of the definition. Perhaps,
←%3((X Y)(PLUS (TIMES X Y) Y)).%*
This is the right approach and it can be made precise.
There is a very elegant and beautiful theory behind this intuitive
discussion. We will sketch a few parts which will be helpful, but
first let's see where we are:
.SS(Review of evaluation)
We have seen that it is possible to mechanize at least one
scheme for evaluation of functions -- left-to-right and call-by-value.
We have seen that it is possible to translate LISP expressions
into Sexprs in such a way that we can write a LISP function
which will act as an evaluator for such translates. In the process
we have had to mechanize the intuitive devices we (as humans) might
use to recall the definition of functions and to recall the current
values of variables. It was soon clear that the same mechanism
could be used: that of symbol tables. To associate a variable with
a value was easy. To associate a function name with its definition
required some care. That is, part of the definition of a function
involves the proper association of formal parameters with the
body of the definition. (We actually need to be a bit more
precise than this in describing recursive functions, but this is
good enough for now.) The device we chose is called the %2lambda
notation%*.
.SS(%3λ%*-expressions,%3λ%*-expressions,P49:)
The λ-notation is a device invented by the logician, Alonzo Church, in
conjunction with his studies in logic and foundations of mathematics.
The λ-calculus is useful for a careful discussion of functions
and is therefore applicable in a purified discussion of procedures in programming
languages.
The notation was introduced into Computer Science by John McCarthy in
the description of LISP.
In the interest of precision we should note that there are actually several
important distinctions between Church's λ-calculus and the notation envisioned
by McCarthy. We will point out a few such discrepancies at the end of this
section.
.BEGIN TURN ON "←";
As we intimated previously, the λ-notation as used in LISP, allows
us to attach names to functions in an unambiguous manner.
We have been very imprecise when writing %3f[x;y]#<=#(x*y#+#y)%* as
a definition of the function %3f%*.
First note that %3f[x;y]%* is %2not%* a function, %3f%* is.
To see what %3f[x;y]%* means consider the following example.
When we are asked to evaluate %3car[(A . B)]%* we say the value is %3A%*.
%3car[(A . B)]%* is an expression to be evaluated; it is a LISP ⊗→form↔←.
If %3car[(A . B)]%* %2is%* a form then so is %3car[x]%*;
only now the value of the
form depends on the current value assigned to the variable %3x%*.
So the %2⊗→function↔←%* is %3car%*; the %2form%* is %3car[x]%*.
The function is %3f%*; %3f[x;y]%* is a form, as is %3x*y#+#y%*.
Also our notation has really been specifying more than just the name.
The notation specifies the formal parameters (%3x%* and %3y%*) and
the order in which we are to associate actual parameters in a call
with the formal parameters of the definition (%3x%* with the first, %3y%* with the second).
More subtly, the notation tells %2which%* variables in the function body
are bound variables. That is, which variables are to expect values when the
function is called. For example define %3g[x]#<=#(x*y#+#y)%*; then the
value of %3g[2]%* is well defined and is itself a function.
***intuitive alpha-conversion****
We wish to have a notation to assign all this other information with the
function body so that function definitions can be inserted into the symbol
table as "values". They will be parametric values, but they will be values.
The λ-notation performs this task by preceding the function body with
a list of the bound variables, called %2⊗→lambda variables↔←%*.
The list of variables is usually referred to as the %2⊗→lambda list↔←%*.
Then this resulting construct is preceeded by "λ[" and followed by "]".
Thus using the above example, the function %3f%* is exactly the
same function as %3λ[[x;y]#x*y#+#y]%*.
We actually need a bit more than
λ-notation to specify recursive functions in a natural manner. See {yonss(P38)}.
The λ-notation introduces nothing new as far as our intuitive binding and
evaluation processes are concerned; it only makes these operations more
precise. So to evaluate a λ-expression, bind the evaluated actual parameters
to the λ-variables and evaluate the function body. Still, evaluation requires
the usual care. For example, is %3λ[[x]2]%* the constant function which always
gives value %32%*? No, it isn't; the evaluation of an expression (form) involving
this function requires the evaluation of the actual parameter associated with %3x%*.
That computation may not terminate. For example, consider %3λ[[x]2][fact[-1]]%*.
where %3fact%* is the LISP implementation of the factorial function given on
{yon(P20)}.
Since we intend to include λ-expressions in our language we must include
a translation of them into sexpression form:
.BEGIN GROUP;TABIT2(25,50);
\%2LISP expression\translation as Sexpr%*
\%3λ[[x%41%*; ...; x%4n%*]%9x%*]\(LAMBDA (X%41%* ... X%4n%*) %1translate of %9x%3)
.END
***fix the following; it is BAD!**
Thus the character, λ, will be translated to %3LAMBDA%*. %3LAMBDA%* is therefore a
kind of prefix operator (like %3COND%*) which allows the evaluator to recognize
the occurrence of a function definition (just as %3COND%* is used by the
evaluator to recognize the occurrence of a (translate of a) conditional
expression).
Here are some examples of %3λ%*-expressions and their evaluation,
followed by some examples of the translation scheme:
.BEGIN NOFILL TABS 10;TURN ON "\";
\%2a. %3λ[[x;y] x%82%* +y][2;3] = 2%82%* + 3 = 7
\%2b. %3λ[[x;y] cons[car[x];y]][(A . B); C] = (A . C)
\%2c. %3λ[[y] cdr[y]][(A B)] = (B)
\%2d. %3λ[[x] car[x]][λ[[y] cdr[y]][(A B)]]
\ = λ[[x] car[x]][(B)]
\ = B
***more examples, cond ,undefined, etc
\%2e. %3λ[[x;y] x%82%* +y] ==> (LAMBDA(X Y)(PLUS (EXPT X 2) Y))
\%2f. %3λ[[x;y] cons[car[x];y]] ==> (LAMBDA(X Y)(CONS (CAR X) Y))
.END
******MORE*******
Our LISP syntax equations should now be augmented to include:
.BEGIN TABIT1(11);GROUP;
<function>\::= λ[<varlist><form>]
<varlist>\::= [<variable>; ... ; <variable>]
\::= [ ]
.END
One of the other more valuable application of λ-notation occurs in that
nebulous area called efficiency. Efficiency is like structured programming --
difficult to define but recognizable when it occurs.
Consider the following sketch of a function definition:
←%3g <= λ[[x][%9p%*[lic[x]] → lic[x]; .... x ...]]%1,
where %3lic%* may be a %dl%*ong %di%*nvolved %dc%*alculation.
We certainly must compute %3lic[x]%* %2once%*. But as %3g%* is defined,
we would compute %3lic[x]%* %2twice%* if p%41%* is true: once
in the calculation of p%41%*; once as e%41%*. Since our
current LISP subset has no side effects, this second calculation
is unnecessary. %3g%* is inefficient. Using λ-expressions, in a style
called %2⊗→internal lambdas↔←%* we can improve %3g%* as follows:
Replace the body of %3g%* with,
←%3λ[y][%9p%*[y] → y; ... x ...][lic[x]]%1. (*1*)
Call this new function %3g'%*:
.BEGIN TABIT2(10,18);GROUP;
\%3g' <= λ[[x]
\\λ[y][%9p%*[y] → y; ... x ... ][lic[x]]
\\ ] %1.
.END
Now when %3g'%* is called we evaluate the actual parameter, binding it
to %3x%*, as always; and evaluate the body, (*1*). Evaluation of (*1*)
involves calculation of %3lic[x]%* %2once%*, binding the result to
%3y%*. We then evaluate the body of the conditional expression as before.
If p%41%* %2is%* true, then this definition of %3g'%* involves
one calculation of %3lic[x]%* and two table look-ups (for the value of %3y%*),
rather than the two calculations of %3lic[x]%* in %3g%*.
More conventional programming languages can obtain the same effect as
this use of internal lambdas by assignment of %3lic[x]%* to an
temporary variable. We will introduce assignment statements in LISP in
{yonss(P37)}.
.END
We complete this section with a brief discussion of the pure λ-calculus
as compared to LISP's application. In the interest of readability, we will
write λ-calculus expressions in a Gothic bold-face type; e.g. %9λ%* and %dx%*
instead of LISP's %3λ%* and %3x%*.
The syntax of (well-formed) %9λ%*-expressions is simple:
.BEGIN TABIT1(10);GROUP;
<wfe> \::= %9λ%* <variable> %d.%* <wfe>
\::= <applic>
<applic>\::= <applic><atom>
\::= <atom>
<atom>\::= <variable>
\::= <constant>
\::= %d(%* <wfe> %d)%*
.END
The interpretation of a %9λ%*-expression is given in terms of simplification
or conversion rules. To present these rules we need a few definitions.
First a variable, %Dx%*, is a %2⊗→free variable↔←%* in a <wfe>, %dE%* if:
.BEGIN INDENT 0,10;GROUP;
%dE%* is the variable, %dx%*.
%dE%* is an application, %d(OP A)%*, and %dx%* is free in %dOP%* and %dA%*.
%dE%* is a %9λ%*-expression, %9λ%dy.M%1, if %dx%* is free in %dM%* and %dx%* is
distinct from %dy%*.
.END
The second definition says a variable is a %2⊗→bound variable↔←%* in %dE%*
if it occurs in %dE%* and is not free in %dE%*.
Finally some notation: %dE[...]%* means that %d...%* is a "well-formed"
sub-expression in %dE%*.
There are three %9λ%*-conversion rules which are of interest here:
.BEGIN INDENT 0,10;
.GROUP;
%9α%*-conversion: %dE[%9λ%*x.M]%1 may be converted to %dE[%9λ%*y.M']%1 if %dy%* is not
free in %dM%* and %dM'%* results from %dM%* by replacing every free occurrence
of %dx%* by %dy%*. %9α%*-conversion allows alphabetic change of free variables.
.APART;
.GROUP;
%9β%1-reduction: %dE[(%9λ%*x.M)N]%1 %9β%*-reducible if no variable which occurs free in %dN%*
is bound in %dM%*. %dE[(%9λ%*x.M)N]%1 is reducible to %dE[M']%* where %dM'%* results
from the replacement of all free occurrences of %dx%* in %dM%* by %dN%*.
Compare call-by-name on {yon(P98)}.
.APART;
.GROUP
%9∂%1-reduction: We may desire a set of %9∂%*-rules which are associated with the
constants appearing in our %9λ%*-language. Each rule has the basic interpretation:
"%dE%* may always be replaced by %dE'%*." The constants and %9∂%*-reduction
rules are used to construct a %9λ%*-calculus for a specific domain of interest.
.APART
.END
Finally we will say that a %9λ%*-expression is in (%9β%*, %9∂%*)
%2normal form%* if
it contains no expression reducible by %9β%*, or %9∂%* rules.
%9α%*-variants are ignored.
This discussion of %9λ%*-calculi is not meant to be definitive; rather it should
convey the spirit of the subject. The discussion is complete enough, however,
to suggest some interesting problems for language design. First, it is apparent
that there may well be two or more sequences of reductions for a %9λ%*-expression;
is there any reason to believe that these reduction sequences will yield
the same normal forms?
Second, if we have two %9λ%*-expressions which reduce
to distinct normal forms, is there any reason to believe that they are
"inherently different" %9λ%*-expressions?
The first question is easier to answer. As we have seen in LISP, the order
in which calculations are performed can make a difference in the final
outcome. So too in %9λ%*-calculi. There, however, we can
show that if both reduction sequences terminate then they
result in the same normal form. This is usually called the Church-Rosser
theorem.
The second question obviously requires some explanation of "inherently different".
At one level we might say that by definition, expressions with different
normal forms are "inherently different".
But a natural interpretation, thinking of %9λ%*-expressions as functions,
is to say two %9λ%*-expressions are distinct if we can exhibit arguments
such that the value computed by one expression applied to the argument is
different from the value computed by the other. Indeed, for %9λ%*-expressions
which have normal forms, C. Boehm has established this.
What can we say about %9λ%*-expressions which do %2not%* have normal forms?
What if we can exhibit two such %9λ%*-expressions, say %df%* and %dg%*,
which are distinct
in that no reduction sequence will reduce one to the other, but our
intuition says that they are "the same function". That is, for any
argument, %da%* we supply, both reductions result in the same expression.
That is %d(f a) = (g a)%*.
The reduction rules of the %9λ%*-calculus cannot help us.
But what should we say if we could
give an interpretation to the %9λ%*-calculus such that in the model our two
wayward expressions have the same meaning? Certainly this should be a convincing
argument for maintaining that they are the "same function" even though
the reduction rules are %2not%* sufficient to display that equivalence
⊗↓This demonstration also gives credence to the position that the
meaning transcends the reduction rules. Compare the incompleteness results
of K. Godel.←.
This, indeed, is the
state of affairs. D. Scott %2has%* exhibited a model or interpretation of
the %9λ%*-calculus, and D. Park has shown the equivalence in this model
of two %9λ%*-expressions which have distinct forms.
What does this discussion have to do with language design? Clearly the order of
evaluation or reduction is directly applicable. What about the second question?
This is related to the problem of characterization of a language. Do you say that
the languago specification consists of a syntactic component and some
(hopefully precise) description of the evaluation of constructs in that language?
Or do you say that these two components, syntax and a machine, are merely
devices for describing or formalizing notions about some abstract domain of
discourse? The study of formal systems in mathematical logic offers a parallel.
There you are presented with a syntax and a system of axioms and rules of inference.
Most usually we are also offered a "model theory" which gives us models or
interpretations for the syntactic formal system; the model theory usually supplies
additional means of giving convincing arguments for the validity of statements
in the formal system. Indeed, the arguments made within the formal system
are couched in terms of "provability" whereas arguments of the model theory are
given in terms of "truth".
C. W. Morris named these three perspectives on language, syntax, pragmatics,
and semantics. I.e.
.BEGIN INDENT 0,10;GROUP;
%2Syntax%*: The synthesis and analysis of sentences in a language. This area is
well cultivated in programming language specification.
.APART
.GROUP
%2Pragmatics%*: The relation between the language and its user.
Evaluators (like %3tgmoaf, tgmoafr, ...%*) come under the heading of pragmatics.
Pragmatics are more commonly referred to as operational semantics in discussions
of programming languages.
.APART
.GROUP
%2Semantics%*: the relation between constructs of the language and the abstract
objects which they denote. This subdivision is commonly referred to as denotational
semantics.
.END
Put differently, syntax describes appearance, pragmatics describes value, and
semantics describes meaning.
Using this classification scheme, most languages are described using syntax, and
a half-hearted pragmatics; seldom does the question of denotation arise.
LISP was described by a syntax and a precise pragmatics; the %9λ%*-calculus
has a simple syntax and precise pragmatics. The work of D. Scott supplies
a semantics for the %9λ%*-calculus; the work of M. Gordon adapts Scott's work
to LISP.
Rest assured that we are not persuing formalization simply as an
end in itself. Mathematical notation is no substitute for clear thought,
but we believe careful study of semantics will lead to additional
insights in language design ⊗↓R. D. Tennent has invoked this approach in
the design of %3QUEST%*.←.
Though the syntax and pragmatics of the %9λ%*-calculus is quite simple,
and it is a most productive vehicle when used to discuss semantics.
As we said at the beginning of the section, this calculus was
intended to explicate the idea of "function" and is therefore a
rarefied discussion of "procedure".
A thorough discussion of the models of the %9λ%*-calculus is beyond the scope of this book,
a few implications are worth mentioning.
There is a reasonably subtle distinction between Church's conception
of a function as a rule of correspondence, and the usual set-theoretic
view of a function as a set of ordered pairs ⊗↓See {yonss(P92)}←.
In the latter setting one rather naturally thinks of the elements of the domain
and range of a function as existing %2prior%* to the construction of the function:
.BEGIN TURN OFF "{","{";
"Let %3f%* be the function {<x,1>, <y,2>, ...}".
.END
Thus in this frame of mind one does not think of functions which can take
themselves as arguments: %3f[f]%*. Such functions are called %2⊗→self-applicative↔←%*.
They are an instance of a common language called procedure-valued variables or
function-valued variables.
See {yonss(P76)} for a discussion of LISP's functional arguments.
The problem on {yon(P99)} is a testimonial to the existence
of self-applicative functions
⊗↓Whether such psychopathic functions are indespensible or even useful
is tangential to our current discussion. But thinking of language design
it is better to deal with them head on rather than simply rule
them out of existence. They may tell us something about the nature of
procedures (functions), and if past history is any indication, banishment
on such prejudical grounds as "Why would anyone want to do a thing like
that?" will not endure.←
Cast in the %9λ%*-calculus setting, self application is approachable.
The conversion rules of the calculus allow a %9λ%*-expression to be
applied to any %9λ%*-expression including the expression %2itself%*.
There are well-known logical difficultiies ⊗↓Russell's paradox.← if we allow
unrestricted self-application.
There are then two difficulties. Can we characterize a useful subset of functions
for which self-application is tractable?
Using this subset, can we find a model for the %9λ%*-calculus
which retains our intuitions about functions.
The discovery of the appropriate class of functions and the model
construction are two of the important aspects of D. Scott's work .
We shall not exhibit Scott's constructions, but in {yonss(P85)} we
shall discuss the class of functions.
M. J. C. Gordon has successfully applied Scott's methods to analyze
subsets of LISP. {yonss(P85)} contains some of the ideas in this
recent work.
.CENT(Problems);
I What is the difference between %3λ[[ ] x*y + y]%* and %3x*y + y%*?
II Write a LISP predicate, %3free <= λ[[x;e]..]%*, which will give %3T%*
just in the case that %3x%* and %3e%* represent a variable and a %9λ%*-expression
respectively, and %3x%* is "free" in %3e%*.
****more probs****
.SS(Mechanization of evaluation,,P6:)
%1
As we have said, %3tgmoaf%* and %3tgmoafr%* ({yonss(P39)}) are evaluators
for subsets of LISP.
Armed with your symbol-table mechanism we could now extend the
%2great-mothers%* to handle variable look-ups.
Rather than do this we will display our burgeoning cleverness
and make a total revision of the structure of the
evaluators. In making the revision, the
following points should be remembered:
1. Expressions (to be evaluated) can contain variables, both simple
variables and variables naming λ-expressions. Thus evaluation must be done
with respect to an environment or symbol table. We wish to recognize other
(translates of) function names besides %3CAR, CDR, CONS, EQ%* and%3 ATOM%*
in our evaluator, but
explicitly adding new definitions to the evaluator in the style of the
recognizers for the five primitives is a bad idea. Our symbol table should
hold the function definitions and the evaluator should contain the general
schemes for finding the definitions, binding variables to values, and
evaluating the function body. By now you should be convinced that this
process is a reasonably well defined task and could be written in LISP.
2. All %2function%* calls are to be evaluated by-value. However there are
some %2⊗→special forms↔←%* we have seen which are not evaluated in the
normal manner. In particular, conditional expressions, quoted expressions,
and lambda expressions are handled differently.
The primary function is named ⊗→%3eval%*↔← rather than %3sogm%* (Son of Great Mother).
It will take two arguments; the first
is a representation of an expression to be evaluated, and the second
is a representation of a symbol table. %3eval%* will recognize numbers, the
constants %3T%* and %3NIL%*, and if presented with a variable, will attempt to
find the value of the variable in the symbol table using %3assoc%* ({yon(P92)}).
%3eval%* also handles the special forms %3COND%* and %3QUOTE%*. If %3eval%* sees
a ⊗→conditional expression↔← (represented by %3(COND ...)%* ) then the body
of the ⊗→%3COND%*↔← is passed to a subfunction named ⊗→%3evcond%*↔←.
%3evcond%* encodes the conditional expression semantics as described on {yon(P40)}. The special
form, ⊗→%3QUOTE%*↔←, signifies the occurrence of a constant. Simply return
that constant.
As far as this %3eval%* is concerned, any other expression is a function-call.
The argument-list evaluation is handled by %3evlis%* in the authorized
left-to-right ordering. This is handled by recursion on the sequence of arguments.
In this case we %2apply%* the function
to the list of evaluated arguments.
This is done by the function %3apply%*.
With this short introduction we will now write a more general evaluator
which will handle a larger subset of LISP than the %3tgm%*s.
Here's the new %3eval%*:
.BEGIN SELECT 3;GROUP;TABIT1(7);
eval <= λ[[exp;environ]
\[isvar[exp] → value[assoc[exp;environ]];
\ isconst[exp] → denote[exp];
\ iscond[exp] → evcond[exp;environ];
\ isfunc+args[exp] → apply[func[exp];evlis[arglist[exp];environ];environ]]
.APART
.GROUP
%1and:%*
denote <= λ[[exp]
\[isnumber[exp] → exp; %1(see footnote {yon(P80)})%3
\ istruth[exp] → exp;
\ isfalse[exp] → exp;
\ isSexpr[exp] → rep[exp]]
.GROUP
%1where:%*
evcond <= λ[[e;environ][eval[ante[first[e]];environ] → eval[conseq[first[e]];environ];
\ T → evcond[rest[e];environ]]]
.APART
.GROUP
%1and,%*
evlis <= λ[[e;environ][null[e] → NIL;
\ T → concat[eval[first[e];environ];evlis[rest[e];environ]]]]
.END
The selectors, constructors and recognizers which relate this abstract
definiton our particular S-expression representation are grouped with
%3apply%* on {yon(P108)}.
The subfunctions, %3evcond%* and %3evlis%*, are simple. %3evcond %*you've seen
before in %3tgmoafr%* in a less abstract form;
%3evlis%* simply manufactures a new list consisting of the
results of evaluating (from left to right) the elements of %3e%*, using the
symbol table, %3environ%*, where necessary.
The left-to-right sequencing should be apparent both in %3evlis%* and %3evcond%*.
A more subtle application of the sequence property occurs
within %3apply%* in the symbol table
search and construction process. We know that %3assoc%* looks from left to right
for the latest binding of a variable. Thus the function which %2augments%* the
table must add the latest binding to the %2front%*. When do new bindings
occur? They occur at λ-binding time, and that time the function %3pairlis%* will
build an augmented symbol table with the λ-variables bound to their evalauted
arguments.
⊗→%3apply%*↔← takes three arguments: a function, a list of evaluated arguments,
and a symbol table. %3apply%* explicitly recognizes the five primitive functions %3CAR,
CDR, CONS, EQ, %*and%3 ATOM%*. If the function name is a variable,
the
definition is located in the symbol table by %3eval%* and applied to the arguments.
Otherwise the function must be a λ-expression. This is where things
get interesting. We know what we must do: evaluate the body of the
λ-expression after binding the formal parameters of the λ-expression
to the evaluated arguments. How do we ⊗→bind↔←? We add variable-value
pairs to the symbol table. We will define a subfunction, %3pairlis%*, to
perform the binding. Then all that is left to do is give the function
body and the new symbol table to %3eval%*. Here is %3apply%*:
.BEGIN SELECT 3;GROUP;TABIT1(15);
.P69:
apply <= λ[[fn;args,environ]
\[iscar[fn] → car[arg%41%*[args]];
\ iscons[fn] → cons[arg%41%*[args];arg%42%*[args]];
\ .... ....
\ isvar[fn] → apply[eval[fn;environ];args;environ];
\ islambda[fn] → eval[body[fn];pairlis[vars[fn];args;environ]]
\ ]]
pairlis <= λ[[vars;vals;environ][null[vars] → environ;
\T → concat[mkent[first[vars];first[vals]];pairlis[rest[vars];rest[vals];environ]]]]
.END
Some of the functions and predicates which will relate these abstact definitions to our
specific S-expression representation of LISP constructs are:
.BEGIN TABIT3(5,28,48);GROUP;SELECT 2;
.P108:
\Recognizer\Selector\Constructor
.SELECT 3;
iscar <= λ[[x]eq[x;CAR]]\func <= λ[[x]first[x]]\mkent <= λ[[x;y]cons[x;y]]
isSexpr <= λ[[x]eq[first[x];QUOTE]]
\\arglist <= λ[[x]rest[x]]
istruth <= λ[[x] eq[x;T]]\body <= λ[[x]third[x]]
\\vars <= λ[[x]second[x]]
.END
So the only really new development is in the λ-binding process.
Notice that %3pairlis%* makes a new symbol table by consing new pairs onto
the front of the old symbol table; and recall that %3assoc%* finds the
%2first%* matching pair in the symbol table. %2This is important.%*
.P86:
To summarize then, the evaluation of an expression %3f[a%41%*; ...a%4n%*]%1
is the same as the result of applying %3eval%* to the sexpr translation
%3(F a%41%** a%4n%**) %1where %3a%4i%1* is the translate of %3a%4i%1.
This behavior is again an example of the diagrams of {yon(P46)}. In its
most simple terms, we mapped LISP evaluation onto the LISP %3eval%* function;
mapped LISP expressions onto S-expressions; executed %3eval%*. Notice
that in this case we do not reinterpret the output since the structure of the
representation does this implicitly. We have commented on the efficacy
of this already on {yon(P110)}.
This specification of the semantics of LISP using %3eval%* and %3apply%*
is one of the most interesting developments of Computer Science.
.CENT(Problems)
I Relate our version of %3eval%* and %3apply%* with the version given in the appendix.
Though the current version is much more readable, how much of it %2still%* depends
on the representation we chose. That is how abstract is it really?
II. Complete the specification of the selectors, constructors, and recognizers.
.SS(Examples of %3eval%*,examples of %3eval%*)
After this onslaught, some examples are in order.
Let's evaluate %3f[2;3]%* where %3f <= λ[[x;y] x%82%* + y].%1
After appropriate translation this is equivalent to evaluating:
←%3eval[(F 2 3);((F . (LAMBDA(X Y)(PLUS (EXPT X 2)Y))))]%*
%2Notes:%*
%21.%* %3((F . (LAMBDA (X Y) ... ))) = ((F LAMBDA (X Y) ... )) %*
%22.%* Since the symbol table, %3((F ...))%* occurs so frequently in the following
trace, we will abbreviate it as %3st%*. Note that we have no mechanism yet
for permanently increasing the repertoire of known functions. We must
resort to the subterfuge of initializing the symbol table to get the function
%3f%* defined.
%23.%* For this example we must assume that + and ↑ (exponentiation) are known functions. Thus
%3apply%* would have to contain recognizers for %3PLUS%* and %3TIMES%*:
.BEGIN NOFILL;
.GROUP
%3
...atom[fn] → [isplus[fn] → +[arg%41%*[arga];arg42*[args]];
isexpt[fn] → ↑[arg%41%*[args];a≤g%42%*[args]];
...
.APART
%1
.END
.BEGIN NOFILL;TABS 10,25;TURN ON "\";
.GROUP
So %3eval[(F 2 3);st]
\= apply[car[(F 2 3)]; evlis[cdr[(F 2 3)];st];st]
\= apply[F;evlis[(2 3);st];st]
\= apply[F;(2 3);st]
\= apply[eval[F;st];(2 3);st]
\= apply[(LAMBDA(X Y)(PLUS (EXPT X 2) Y)); (2 3);st]
\= eval[caddr[(LAMBDA(X Y)(PLUS (EXPT X 2) Y))];
\ pairlis[cadr[(LAMBDA(X Y)(PLUS (EXPT X 2) Y))];(2 3);st]]
\= eval[(PLUS (EXPT X 2) Y);pairlis[(X Y);(2 3);st]]
\= eval[(PLUS (EXPT X 2) Y);((X . 2)(Y . 3)(F LAMBDA(X Y) ...))]
\= apply [PLUS; evlis[((EXPT X 2) Y);((X . 2)(Y . 3)..)];((X . 2)...)]
\ %1Let's do a little of:%3 evlis[((EXPT X 2)Y);((X . 2)(Y . 3)...)]
\\= cons[eval[(EXPT X 2);((X . 2)(Y . 3) ...)];
\\ evlis[(Y);((X . 2) ...)]]
\\= cons[apply[EXPT;evlis[(X 2);((X . 2)...)];((X . 2) ...]
\\ evlis[(Y); ...]]
\\= cons[apply[EXPT;(2 2);((X . 2) ...];evlis[(Y); ...]]
\\= cons[↑[car[(2 2)];cadr[(2 2)]];evlis[(Y); ... ]]
\\= cons[↑[2;2];evlis[(Y); ... ]]
\\= cons[4;evlis[(Y);((X . 2)(Y . 3) ....)]]
\\= cons[4;cons[eval[Y;((X .2) ...)]; evlis[NIL;(( ...))]]]
\\= cons[4;cons[3;NIL]]
\\= (4 3) %1 which you knew anyway.
Now back to apply:
%3
\= apply[PLUS;(4 3);((X . 2)(Y . 3) ... )]
\= +[4;3]
\= 7 %1which you also knew.
.APART
.END
It should now be clear that %3eval%* and friends %2do%* begin to
perform as you would expect. It perhaps is not clear that a
simpler scheme might not do as well. In particular, the complexity
of the symbol table mechanism which we claimed was so important
has not been exploited. The next example will indeed show that a
scheme like ours is necessary to keep track of variable bindings.
.GROUP
Let's sketch the evaluation of %3fact[3]%* where:
←%3fact <= λ[[x][x = 0 → 1;T → *[x;fact[x-1]]]].%*
.P42:
That is, %3eval[(FACT 3);st] %*where %3st%* names the initial symbol table,
←%3((FACT LAMBDA(X)(COND((ZEROP X)1)(T(TIMES X(FACT (SUB1 X))))))).%1
.APART
In this example we will assume that the binary function, *, the
unary predicate, %3zerop#<=#λ[[x]x#=#0]%* and unary function,
%3 sub1#<=#λ[[x]#x-1]%* are known and are
recognized in the evaluator by %3TIMES, ZEROP%* and %3SUB1%* respectively.
.BEGIN NOFILL;TURN ON "\";TABS 10,20,30;
.GROUP
%1Then%3 eval[(FACT 3);st]
\= apply[FACT;evlis[(3);st];st]
\= apply[(LAMBDA(X)(COND ...));3;st]
\= eval[(COND((ZEROP X)1)(T( ...)));((X . 3) . st)]
\= evcond[(((ZEROP X)1)(T(TIMES X(FACT (SUB1 X)))));((X . 3) . st)]
%1(Now, let %3st1%* be%3 ((X . 3) . st) )
\= eval[(TIMES X(FACT (SUB1 X))); st1]
\= apply[TIMES;evlis[(X (FACT (SUB1 X))); st1];st1]
\= apply[TIMES;cons[3;evlis[((FACT (SUB1 X))); st1];st1]
%1Now things get a little interesting inside %*evlis:
\evlis[(((FACT (SUB1 X)));st1]
\\= cons[eval[(FACT (SUB1 X)); st1];NIL]
\\%1 and %* eval[(FACT (SUB1 X));st1]
\\\= apply[FACT;evlis[((SUB1 X));st1];st1]
\\\= apply[FACT; (2);st1]
\\\= apply[(LAMBDA (X)(COND ...));(2);st1]
\\\= eval[(COND((ZEROP X) 1) ...));((X . 2) . st1)]
\\\...
.APART
.FILL
%1
Notice that within this latest call on %3eval%* the symbol-table-searching function,
%3assoc%*, will find the pair %3(X . 2)%* when looking for the value of %3x%*. This is
as it should be. But notice also that the older binding, %3(X . 3)%*, is still
around in the symbol table %3st1%*, and will become accessible once we complete
this latest call on %3eval%*.
.GROUP
As the computation continues, the symbol table is proceeding initially from,
.NOFILL
%3
←st =((FACT LAMBDA(X)(COND ...))) %1to%3,
←((X . 3) . st) %1to%*,
←((X . 2)(X . 3) . st) %1to%*,
←((X . 1)(X . 2)(X . 3) . st) %1to finally%*,
←((X . 0)(X . 1)(X . 2)(X . 3) . st).
%1
.FILL
.APART
Since the search function, %3assoc%1, always proceeds from left to right through
the table and since the table entry function, %3pairlis%*, always %3cons%*es pairs
onto the front of the table before calling %3eval%*, we will get the correct
binding of the variables.
This symbol table mechanism is very important, so let's look at it
again in a slightly different manner.
.END
.<<the | | symbol table >>
.P43:
We will represent calls on %3eval%* informally, using LISP expressions
rather than Sexprs as input. We represent the symbol table between vertical
bars, "|", in such a way that if a table, t%41%*, is:
.BEGIN TABIT2(10,17);GROUP
\| b%4n%*\|
\| ...\| then %3cons%*ing a new element, b%4n+1%* onto t%41%* gives:
\| b%41%*\|
\| b%4n+1%*\|
\| b%4n%*\|
\| ...\|
\| b%41%*\|
.END
%3
.BEGIN NOFILL;TABS 10,46,58;TURN ON "\";
%1Then:%*
eval[`fact[3]'; |fact = λ[[x][x=0 → 1;T → *[x;fact[x-1]]]]|]
.GROUP
\= eval[`λ[[x][x=0 → 1; T → *[x;fact[x-1]]]];\|x = 3 | ]
\\|fact = λ[[ ... |
.APART
.GROUP
\= *[3;eval[`λ[[x] ....'; \| x = 2 |]
\\| x = 3 |
\\|fact = λ[[ ...] |
.APART
.GROUP
\= *[3; *[2;eval[`λ[[x] ... ';\| x = 1 |]
\\| x = 2 |
\\| x = 3 |
\\|fact = λ[[ ... |
.APART
.GROUP
\= *[3; *[2; *[1;eval[`λ[[x] ... ';\| x = 0 |]
\\| x = 1 |
\\| x = 2 |
\\| x = 3 |
\\|fact = λ[[ ... |
.APART
.GROUP
\= *[3; *[2; *[1;1]]] %1with:%*\| x = 1 |
\\| x = 2 |
\\| ... |
.APART
.GROUP
\= *[3; *[2;1]] %1with:%*\| x = 2 |
\\| ... |
.APART
.GROUP
\= *[3;2] %1with:%*\| x = 3 |
\\| ... |
\= 6. %1with:%*\|fact = λ[[ ... |.
= 6
.END
%1
Notice that after we went to all the trouble to save the old values
of %3x%* we never had to use them. However, in the general case of
recursive evaluation we must be able to save and restore the old values
of variables.
For example recall the definition of %3equal:
.BEGIN NOFILL TURN ON "\";TABS 17;
.GROUP
%3
equal <= λ[[x;y][atom[x] → [atom[y] → eq[x;y];T → NIL];
\ atom[y] → NIL;
\ equal[car[x];car[y]] → equal[cdr[x];cdr[y]];
\ T → NIL]]
.APART
%1If we were evaluating:%3
←equal[((A . B) . C);((A . B) . D)],
%1
then our symbol table structure would be changing as follows:
.END
%3
.BEGIN NOFILL;TABS 10,40;TURN ON "\";
.GROUP
\|equal = λ[[x;y] ...| ==>\|x = ((A . B) . C)| ==>
\\|y = ((A . B) . D)|
\\|equal = λ[[x;y]... |
.APART
.GROUP
\| x = (A . B) |\| x = A |
\| y = (A . B) |\| y = A |
\| x = ((A . B). C)| ==>\| x = (A . B) |
\| y = ((A . B). D)|\| y = (A . B) | ==>
\|equal = λ[[x;y ... |\| x = ((A . B). C) |
\\| y = ((A . B). D) |
\\|equal = λ[[x;y] ...|
.APART
.GROUP
\| x = B |\| x = C |
\| y = B |\| y = D |
\| x = (A . B) |\| x = ((A . B). C) | ==>
\| y = (A . B) | ==>\| y = ((A . B). D) |
\| x = ((A . B). C) |\|equal = λ[[x;y] ... |
\| y = ((A . B). D) |
\|equal = λ[[x;y] ... |
←|equal = λ[[x;y] ... |
.END
%1
This complexity is necessary, for while we are evaluating
%3equal[car[x];car[y]]%*, we rebind %3x%* and %3y%* but we must save the old
values of %3x%* and %3y%* for the possible evaluation of %3equal[cdr[x];cdr[y]].%*
But the claim is that using %3pairlis%* to cons the new
bindings onto the front of the symbol table as we call %3eval%*
does the right thing. That is, in %3apply%* ({Yon(P69)}):
%3
←islambda[fn] → eval[body[fn];pairlis[vars[fn];args;environ].
%1
The tricky part is that when we leave that particular call on
%3apply%*, the old table is automatically restored by the recursion
mechanism. That is, if %3st%* is the current symbol table then
%3cons%*-ing things onto the front of %3st%* doesn't change %3st%*, but if we
call %3eval%* or %3apply%* with a symbol table of say:
←%3cons[(X . 2);cons[(X . 3); st]] %*
then in %2that%* call on %3eval%* or %3apply%* we have access to %3x = 2%*, not
%3x = 3%*.
.P93:
Before moving on we should examine %3eval%* and %3apply%* to see how the
compare with our previous discussions of LISP evaluation.
The spirit of call-by-value and conditional expression evaluation is maintained.
λ-binding seems correct, though our current discussion is not complete.
At least one preconception is not maintained here. Recall the discussion on
{yon(P95)}. We wanted n-ary functions called with exactly n arguments. An
examination of the structure of %3eval%* and %3apply%* shows that
if a function expecting %2n%* arguments is presented with less, then
the result is undefined; but if it is given %2more%* than necessary
then the calculation is performed. For example:
.BEGIN TABIT1(33);GROUP;SELECT 3;
eval[(CONS(QUOTE A)(QUOTE B)(QUOTE C));NIL]
\= eval[(CONS(QUOTE A)(QUOTE B));NIL]
\= (A . B)
.END
This shows one of the pitfalls in defining a language by an evaluator.
If the intuitions of the language specifiers are faulty or incomplete
then we are faced either with maintaining that faulty judgement as if nothing
were wrong; or we must lobby for a "revised report". Neither alternative
says much for the field of language design.
.BEGIN TURN ON "#";
Let's look more closely at λ-binding. The scheme presented seems reasonable,
but as in the case above, there is more going on here than we are perhaps
aware of. In particular, we are thinking of the question of %2⊗→free variable↔←s%*.
Consider the function: %3λ[[x]x#+#y]%*. The variable %3x%* is called a
%2⊗→bound variable↔←%*; the variable %3y%* is a free variable. When we
apply this function, we will associate %3x%* with the value of the actual
parameter, but this λ-binding will not effect %3y%*. Clearly, %3y%*'s
value will determine the course of the computation. For example, if %3y%*
has value %31%*
then our function is %3add1%*, if %3y%*'s value is %3-1%*, then %3sub1%*.
How are we to give a value to %3y%*? We do so by λ-binding.
For example %3 λ[[y]#λ[[x]x#+#y][2]][1]%* binds %3y%* to %31%* and
then %3x%* to %32%*. Rest assured (though you should convice yourself) that
%3eval%* handles free or ⊗→global variable↔←s consistent with this interpretation.
Handling of global variable varies from programming language to programming
language. The solution introduced by LISP is called %2⊗→dynamic binding↔←%*.
This binding strategy advocates evaluation of free variables at the time
of activation of the function rather than at the time of definition
of the function ⊗↓The latter solution is used in ALGOL 60.←.
Conceptually, the dynamic binding scheme corresponds to the physical
replacement of the function call with the function body and then an
evaluation of the resulting expression.
We first wish to develop a useful notation before delving further into
the intracacies of binding strategies.
.END
.CENT(Problems)
%2I%* Which parts of %3eval%* and Co. allow correct evaluation functions
applied to too many arguments?
%2II%* On {yon(P93)} we noted that the evaluator performs "correctly"
when evaluating forms like %3cons[A;B;C]%*.
Can you find other anomalies in %3eval%* and friends?
.SS(Environments and bindings,,P77:)
.<< the Weizenbaum symbol table>>
This section will introduce one more notation
for describing symbol tables or environments. This notation, due to
J. Weizenbaum, only shows the abstract structure of the symbol table manipulations
during evaluation. Its simplicity will be of great benefit when we introduce
more complex binding schemes necessary for function-valued functions.
See {yonss(P76)}.
In the previous discussions it has been sufficient
simply to think of a symbol table as a sequence pairs; each pair was a variable
and its associated value. First, we survived beacuse we dealt only with
local variables ⊗↓λ-variables←. As long as we added the λ-bindings to the
%2front%* of the sequence representing the symbol table we showed that the
correct evaluation would result.
Even after we recognized the existence of %2global%* variables, we survived
because of LISP's generous dynamic binding scheme.
However with the advent of global variables, it is convenient and soon
will be necessary, to examine the structure of environments more closely.
The evaluation of a typical form will involve the evaluation of variables.
Variables which are local to a form-evaluation are those which were
present in the preceding λ-binding. All other variables are global.
We will describe our environments in terms of a local symbol table
augmented by a description of where to find the global values.
Thus instead of having one amorphous sequential symbol table, we
envision a sequence of tables. One is the local table, and its
successor in the sequence it the previous local table. The
information telling where to find the previous table is called the
%2⊗→access chain↔←%*. LISP thus finds local bindings in the local
table and uses the access chain to find bindings of global variables.
If a variable is not found in any of the tables, then it is undefined.
Now to establish some notation,
an environment will be described as :
.BEGIN TABIT2(36,40);GROUP;
\\%aForm%*
\\E%4local%*
\\|
\ \| E%4i%*
\_________
\var\| value
\%3v%41%1\| %aval%41%1
\%3v%42%1\| %aval%42%1
\ .....
\%3v%4n%1\| %aval%4n%1
\\|
.END
%aForm%* is the current form being evaluated.
E%4local%* is the name of the current environment or symbol table.
Let %3%* be a variable appearing in %aForm%*. If %3x%* is not found
among the %3v%4i%1's,
then entries in the table named E%4i%* are examined.
If the variable is not found
in E%4i%* then the environment mentioned in the upper right-hand quadrant
of E%4i%* is searched. The search will terminate if the variable is found;
the value is then the corresponding %aval%4i%1.
If %3x%* is not found locally, and the symbol "/" appears in
the right-hand quadrant, then %3x%* is undefined.
The notation is used as follows: when we begin the evaluation of a
form, an initial table E%40%* is
set up with "/" in its access field.
The execution of a function definition, say %3f#<=#λ[[x;y]x%82%*#+#y]%1, will
add an appropriate entry to the table, binding %3f%* to its lambda definition.
Next, consider the evalaution of the form %3f[2;3]%*.
When the λ-expression is entered, i.e.,
when we bind the evaluated arguments (%32%* and %33%*) to the
λ-variables (%3x%* and %3y%*), a new local table (E%41%*) is set up
with an access link of E%40%*.
Entries reflecting the binding of the λ-variables are made in E%41%* and
evaluation of the λ-body is begun.
The flow of symbol tables is:
.BEGIN TURN ON "\";NOFILL;TABS 10,13,18,23,26,41,46,49,54,57,60,65,70,73;
.GROUP
\\%3f <= ...\\\f[2;3]\\\x%82%* + y%1
\\E%40%*\\\E%40%*\\\E%41%*\\\E%40%*
\ \| /\\ \| /\\ \| E%40%*\\ \| /
\______\=>\______\=>\______\=>\______
\\|\ \ %3f\| λ[[x;y]x%82%* + y]%1\ \%3x\| 2\ \f\| λ[[x;y] ...
\\\\\\\ y\|3%1
.APART
.FILL;
The execution of %3fact[3]%* on {yon(P42)} results in a more interesting
example.
.P104:
.BEGIN TURN ON "\";NOFILL;TABS 10,13,18,23,26,31,36,39,44,47,50,55,60,63;
.GROUP
\\%3fact[3]\\\fact[2]\\\fact[1]\\\fact[0]\\\x%1
\\E%40%*\\\E%41%*\\\E%42%*\\\E%43%*\\\E%44%* ...etc.
\ \| /\\ \| E%40%*\\ \| E%41%*\\ \| E%42%*\\ \| E%43%* ...
\______\=>\______\=>\______\=>\______\=>\______
\%3fact\| λ[[x] ...\ x\| 3\\ x\| 2\\ x\| 1\\ x\| 0 ...%1
.END
Notice in this example we will get the correct binding of %3x%* locally.
Is it important to note that the occurrence of %3fact%* within the body of
the definition of %3fact%* is %2global%*! We find the correct binding
for %3fact%* by searching the access chain.
.GROUP
As a final example showing access to ⊗→free variable↔← bindings consider:
%3f[3]%* where: %3 f <= λ[[x]g[2]]%* and %3g <= λ[[y] x+y]%*.
.NOFILL;
\%3f <= ...; g <= ...\\f[3]\\\g[2]\\\x + y ....
\\E%40%*\\\E%40%*\\\E%41%*\\\E%42%* ....
\ \| /\\ \| /\\ \| E%40%*\\\| E%41%*
\______\=>\______\=>\______\=>\______\ ......
\\|\\ %3f\| λ[[x] g[x]]\\%3x\| 3\ \y\| 2 ...
\\\\%3g\| λ[[y] x+y]
.END
Notice that when we attempt to evaluate %3x + y%* we find %3y%* has a local
value, but we must look down the access chain to find a binding for %3x%*.
The scheme for using Weizenbaum environments for the current LISP subset
should be clear. When doing a λ-binding, set up a new E%4new%* with
the λ-variables as the local variable entries and the values of the
arguments as the corresponding value entries. In this interpretation, "<="
is just another λ-binding. The access slot of the new E%4new%* points
to the previous symbol table. The evaluation of the body of the
λ- expression takes place using the new table; when a local variable
is accessed we find it in E%4new%*; when a global variable occurs, we
chase the access chain to find its value.
When the evaluation of the form is completed, E%4new%* disappears
and the previous environment is restored.
Obviously you should convince yourself that the current access- and binding-scheme
espoused by LISP is faithfully described in these diagrams.
.REQUIRE "PROB8.PUB" SOURCE_FILE;
.SS(%3label%*,%3label%*,P38:)
One effect of placing "λ" and a list of λ-variables in front
of an expresson is to bind those variables which appear both in
the λ-list and the expression. All other variables
appearing in the expression are %2⊗→free variables↔←%*.
For example, %3f%* is free in the following:
←%3f <= λ[[x][zerop[x] → 1; T → *[x;f[x-1]]] ].%1
Clearly our intention is that the %3f%* appearing the the right of "<="
is the same %3f%* appearing to the left of "<=". That is we want %3f%* to be
a bound variable and not free.
This has not been a problem for us. We have simply pre-loaded the
symbol table, binding %3f%* to its definition (or value). See {yon(P42)}. LISP
has been equipped with a slightly more elegant device for this binding.
It is called the %3label%* operator. It is called thus:
←%3label[%1<identifier>;<function>]
and has exactly the effect of binding the <identifier> to the <function>.
To include %3label%* in the LISP syntax add:
.BEGIN TABIT1(11);CENTERIT;
<function>\::= %3label%*[<identifier>;<function>]
and the sexpr translation of the %3label%* construct should naturally be:
←%3(LABEL %1translate of <identifier> translate of <function> %3)%1.
Note that %3label%* should be a special form.
.END
.BEGIN TURN ON "#";
With the introduction of %3label%* we can talk more precisely about "<=".
When we write "what is the value of %3f[2;3]%* when %3f#<=#λ[[x;y]#...#]%*?"
we mean: evaluate the form %3[label[f;#λ[[x;y]#...]][2;3]]%*. If %3f%*
is not recursive, then the %3label%* application is unnecessary. The
anonymous function %3λ[[x;y]#...#]%* applied to %3[2;3]%* suffices.
What about statements like "evaluate %3g[A;B]%* where
%3g#<=#λ[[x;y]#...#f[u;v]#...]%* and %3f#<=#λ[[x;y]#...#]%1."?
%3label%* defines only one function; we may not say %3label[f,g;#...#]%*.
What we %2can%* do embed the %3label%*-definition for %3f%* within
the %3label%*-definition for %3g%*⊗↓Indeed %2every%* occurrence of %3f%*
must be replaced by the %3label[f;...]%1construct.←. Thus:
.BEGIN CENTER;SELECT 3;
label[g;#λ[[x;y]#...#label[f;#λ[[#...#]#...#][u;v]#...]%*
.END
The perspicuity of such constructions is minimal. Needless to say,
implementations of LISP offer better definitional facilities.
.END
The apparent simplicity of the %3label%* operator is partly due to
misconception and partly due to the restrictions placed on the current
subset of LISP. %3label%* appears to be a
rather weak form of an assignment statement. When we extend LISP to include
assignments we can easily show that such interpretation of %3label%* is
insufficient;
when we talk about a mathematical interpretation of LISP
we will show that %3label%* really requires careful analysis.
.CENT(Problem);
I. Show one way to change %3eval%* to handle %3label%*.
II. Express the definition of %3reverse%* given on {yon(P97)} using
%3label%*.
.BEGIN GROUP;
III Evaluate the following:
.SELECT 3;CENTERIT;
←λ[[y]label[fn;fn%42%*][NIL]] [NIL]
where:
←fn%42%* <= λ[[x][y → 1; x → 2; T → fn%41%*[T]]
←fn%41%* <= λ[[y]fn[y]]
.END
.SS(Functional Arguments and Functional Values,functional argument,P76:)
.BEGIN TURN ON "#","←";
Recall our discussion of :
%3eval[(F#2#3);((F#.(LAMBDA(X#Y)(PLUS#(EXPT#X#2)Y))))].%*
We now know this is equivalent to:
%3eval[((LABEL#F#(LAMBDA(X#Y)(PLUS#(EXPT#X#2)#Y)))#2#3);NIL]%1.
In either case, the effect is to bind the name %3f%* to the λ-expression.
Binding is also going on when %3f%* is called: we bind %32%* to %3x%*, and %33%*
to %3y%*. Acknowledging Occam, why not attempt to combine the binding processes?
For example if %3 twice[x]%* is defined to be %3plus[x;x]%*, and %3foo[f;x]%*
were %3f[x]%*, then a truly expensive way of evaluating %3twice[2]%* would appear
to be %3foo[twice;2]%*.
.P81:
This will almost work; as usual %3foo%* would be considered a %2function%* by %3eval%*
and the arguments would be evaluated. We don't want the %2value%* of %3twice%*, we
want the %2name%*. So to stop evaluation, we might try %3QUOTE%*-ing %3twice%* when
we call %3foo%*; thus %3foo[#TWICE;#2]%*. %3QUOTE%*-ing is not quite
good enough, as we will see in a moment, but it would work here. %3f%* in the definition
of %3foo%* is called a %2functional argument%*; %3f%* is a λ-variable, but appears
in the body of the function where we expect a function. You, of course,
should realize by now that %2all%* function names appearing in our LISP expressions
are variables; hopefully they are bound to %2something%* (primitives or λ-expressions)
before we attempt to evaluate them.
Using Weizenbaum's environments we might get:
.BEGIN GROUP;TURN ON "\";NOFILL;TABS 10,13,23,28,31,46,51,54,59,62,65;
\%3foo[TWICE;2]\\\f[x]\\\ x + x%*
\\E%40%*\\\E%41%*\\\E%42%*
\ \| /\\ \| E%40%*\\ \| E%41%*
\______\=>\______\=>\______
%3 twice\\| λ[[x] x + x\\ x\| 2\\ x\| 2
%3 foo\\| λ[[f;x] f[x]]\\ f\| TWICE
%1So we %2will%* get the right bindings.
.END
If such baroque examples were the limit of functional arguments, their usefulness
would be questionable, however they are both a powerful programming tool and their
implementation sheds much light on programming language design (see {yonss(P3)}).
Perhaps a more intuitive and useful application of functional arguments
would be a function to manufacture the composition of two functions:
For example:
.BEGIN CENTERIT;SELECT 3;GROUP;
←compose[car;cdr] = cadr
%1with a plausible definition as:%3
←compose <= λ[[f;g]λ[[x]f[g[x]]]
.END
Clearly our current conception of LISP has to be modified if such creatures
are to be allowed. The body of %3compose%* is a function, not a form, so
the syntax equations must be modified and an extension to %3eval%* and
friends must be made. Syntax, as usual, is trivial. But how are we
to interpret functional arguments (%3twice%* in %3foo[twice;2]%*),
and functional values (%3λ[[x]f[g[x]]]%* in the body of %3compose%*)?
As we intimitated a moment ago, %3QUOTE%*-ing "almost" works, but "almost"
in programming isn't good enough.
The problems with functional arguments and functional values arise
from occurrences of
global variables. %3f%1 and %3g%* in %3compose%* are global, or free, variables.
When there are no free variables in the function, %3QUOTE%* will suffice, but
since the interesting applications of such functions usually involve
global variables, we must deal with them.
First let's look at functional arguments. For the moment we will distinguish
functional arguments by bracketing them with "-marks.
Let %3fn <= λ[[x%41%*; ... ;x%4n%*] %9x%3(y)]%1 be a function which will be used
as a functional argument in the context, say:
.BEGIN SELECT 3; CENTERIT;GROUP;
%1evaluate:%*
←λ[[y] ... fie[2;"fn"] ...][1]
%1where:%*
←fie <= λ[[y;foo] .... foo[a%41%*; ...;a%4n%3] ... ]
.END
Notice that %3y%* is %2free%* in the definition of %3fn%*; %3y%* is initially
bound to %31%* since it is a λ-variable in the original form; and %3y%* is
re-bound to %32%* when we enter %3fie%*. Notice,too, that the variable %3foo%*
appears in a function-position within the body of %3fie%*.
When we finally get around to evaluating, %9x%3(y)%1 ⊗↓the body of %3fn%*←,
how are we to
evaluate %3y%*? Our dynamic-binding scheme would attribute the value %32%*
to %3y%* since that would be the latest binding for %3y%*. But is that
the binding we want? Not likely.
Consider, %3baz[..."compose[sin;cos]" ...]%*. If somewhere within the
body of %3baz%* we redefine %3sin%* or %3cos%* we don't want the
effect of the composition to be effected. What we want is the binding
of the free variables %2at the time the functional argument is recognized%*
not at the time that it finally gets applied.
The necessary mechanics for doing the bindings will require
a modification to the Weizenbaum environments.
Consider the call %3fie[2;"fn"]%*. As before, we must set up a new environment,
E%4fie%*, with access link E%4current%*, binding %3y%* to %32%*.
But we must associate %2two%* pieces of information with %3foo%*:
the λ-definition, and the environment, E%4current%*.
Thus:
.BEGIN TABIT2(36,40);GROUP;
\\E%4fie%*
\\|
\ \| E%4current%*
\_________
\var\| value
\%3y%1\| %32
\%3foo%1\| %3λ[[x%41%*; ... ;x%4n%*] %9x%3(y)]%1E%4current%*
\\|
.END
When we finally see %3foo[ ...]%* within the body of %3fie%*,
we find the λ-definition in E%4fie%*, as before, but now we
set up the access link to E%4current%* before evaluating %9x%3(y)%1!
Thus:
.BEGIN TABIT2(36,40);GROUP;
\\%9x%3(y)%1
\\E%4new%*
\\|
\ \| E%4current%*
\_________
\var\| value
\%3x%41%1\| ...
\%3x%42%1\| ...
\...\|...
\%3x%4n%1\| ...
\\|
.END
Recall the use of Weizenbaum environments on {yon(P104)} to show
the evaluation of %3fact[3]%1. That must now be modified to attach
the appropriate environment to the λ-definition.
.BEGIN TURN ON "\";NOFILL;TABS 10,13,18,23,26,31,36,39,44,47,50,55,60,63;
.GROUP
\\%3fact[3]\\\fact[2]\\\fact[1]\\\fact[0]\\\x%1
\\E%40%*\\\E%41%*\\\E%42%*\\\E%43%*\\\E%44%* ...etc.
\ \| /\\ \| E%40%*\\ \| E%40%*\\ \| E%40%*\\ \| E%40%* ...
\______\=>\______\=>\______\=>\______\=>\______
\%3fact\| λ[[x] ...:%1E%40%3\ x\| 3\\ x\| 2\\ x\| 1\\ x\| 0 ...%1
.END
Notice that the access links are all the same.
Before toasting our brilliance, we must sorrowfully note that we are not
finished yet! There is still some information which we must make explicit
if these diagrams are to faithfully represent the process of evaluation.
Namely: after we have finished the evaluation of %9x%3(y)%1 we are to
restore a previous environment. Which one is it? It isn't E%4current%*,
it's E%4fie%1! That information is not available in our diagram, so
clearly we must correct the situation.
The solution is clear. In the left-hand quadrant of our diagram we
place the name of the environment which we wish restored when we leave the
current environment.
That environment name will be called the %2⊗→control environment↔←%*;
and will head a chain of control environments, called the control chain
⊗↓In Algol, the access chain is called the static chain, and the control
chain is called the dynamic chain.←.
Now we can relax. Here's the correct picture:
.BEGIN TABIT2(36,40);GROUP;
\\%9x%3(y)%1
\\E%4new%*
\\|
\E%4fie%1\| E%4current%*
\_________
\var\| value
\%3x%41%1\| ...
\%3x%42%1\| ...
\...\|...
\%3x%4n%1\| ...
\\|
.END
This solution might seem a bit drastic, but it is easy to construct
counterexamples to less sophisticated solutions.
For example, attempting to substitute value for the free variables at the time
"<=" is done is not sufficient.
Consider the following example:
.BEGIN TURN ON "\";NOFILL;TABS 10,13,28,33,36,51,56,59,64,67,70;GROUP;
\\%3g[3]\\\f[2]\\\x + y + z ....%1
\\E%40%*\\\E%41%*\\\E%42%* ...
\ /\| /\\E%40%*\| E%40%*\\E%41%*\| E%40%* ....
\______\=>\______\=>\______ ....
\%3f\| λ[[x]x+y+z]:%1E%40%3\\y\| 3\\x\| 2
\g\| λ[[y]f[2]]
\z\| 4
.END
Notice that we could substitute the value for %3z%* when %3f%* is defined
but we cannot do so for %3y%*. Even if there were a value for %3y%* at this time
it would be the wrong value.
What does this say about functions? We have already remarked that functions are
parametric values; to that we must add that functions are also tied to the environment
in which they were created; they cannot be evaluated %3in vacuo%*.
.P89:
What does this say about "<="? It %2still%* appears to act like an assignment statement.
It is taking on more distinct character since it must associate environments with
the function body as it does the assignment.
The device LISP used to associate environments with functions is called
the ⊗→%3FUNARG%*↔← hack. (More is said about %3FUNARG%* in {yonss(P3)}.)
Instead of designating an instance of a functional argument by the %3QUOTE%*
operator, we introduce a new operator called ⊗→%3FUNCTION%*↔←. Thus:
←%3function[λ[[x]f[g[x]]] %*or,
←%3(FUNCTION(LAMBDA(X)(F(G X)))).%*
When %3eval%* sees the construction %3(FUNCTION %1fn%3)%* it returns as value
the list:
←%3(FUNARG###%*fn### current-symbol-table%3)%*.
When %3eval%*, or actually %3apply%* sees %3(FUNARG %*fn st%3)%*, that is,
when we are %2calling%3 fn%1, we use the symbol table %3st%*, rather than
the current symbol table for accessing global variables.
.<<pic of funarg execution>>
.P79:
Let's follow the behavior of an %3eval%* and %3apply%* family which
has been modified to handle functional arguments.
Let %3fn <= λ[[x%41%*; ... ;x%4n%*] ...]%1 be a function which will be used
as a functional argument in the context, say:
.BEGIN SELECT 3; CENTERIT;GROUP;
←fie <= λ[[ ...;foo ...] .... foo[ ...] ]
←fie[ ...; function[fn]; ...]
.END
in the sequel %3st%* and %3st%4save%1 will name symbol tables. "→" will mean
"points to" (i.e.,#%3cons%*). p%4i%*'s will be dotted pairs in a symbol table.
Then let's see what calling %3fie[#...;#function[fn];#...]%* will do.
.BEGIN TABIT2(10,60);GROUP
\%3(FIE ... (FUNCTION FN) ...) st:\NIL ⊗↓%3st%1 is not really empty.
Obviously it contains the function definitions.←
\ ....
\%1computation %3st%1 :\p%4n%* → p%4n-1%* → ... p%41%*
\%3(FUNCTION FN)
\%1 gives:
\%3(FUNARG FN st%4save%*)
\ ....
\%1computation %3st%1 : p%4m%* → p%4m-1%* ...→
\%3(FOO %1a%41%* ... a%4n%*)
\%1 gives:
\%3((FUNARG FN st%4save%*)%1a%41%* ... a%4n%3)
.BEGIN FILL;NARROW 0,40;
%1The a%4i%*'s are evaluated in the context %3st%* %2not%* %3st%4save%1 by
%3evlis[#...;#st]%* giving v%4i%1's.
We then apply %3fn%* to the v%4i%*'s in the context %3st%4save%1 %2not%*
in environment %3st%* by calling %3apply[#...#;#...#;st%4save%*].
%1This results in:
%3eval[ %1body of %3fn%*; %3((x%41%1 . v%41%3) → ... (x%4n%1 . v%4n%3)%1 → #####]
.END
.END
After we finish this inner call on %3apply[#...#;#...#;st%4save%*]%1 the table %3st%*
is restored. Notice that our symbol tables are now really tree-like rather than
stack-like.
It should be apparent from %3eval%* that %3(QUOTE#...)%*
and %3(FUNCTION#...)%* will have the
same effect if %3fn%* has no global (or free) variables.
This seems like a lot of work to allow a moderately obscure construct to appear in a language.
However constructs like functional arguments appear in several programming languages
under different guises. Usually the syntax of the language is sufficiently
obfuscatory that the true behavior and implications of
devices like functional arguments is misunderstood. Faulty implementations
usually result. In LISP the problem %2and the solution%* appear
with exceptional clarity.
Functional arguments may be exploited to describe very general control structures.
We will say more about this application later.
Finally, here is a sketch of the abstract structure of the current %3eval%*.
.BEGIN SELECT 3;GROUP;TABIT1(12);
eval <= λ[[exp;environ]
\[isvar[exp] → value[exp;environ];
\ isconst[exp] → denote[exp];
\ iscond[exp] → evcond[exp;environ];
\ isfun[exp] → makeclosure[exp;environ];
\ isfunc+args[exp] → apply[func[exp];evlis[arglist[exp];environ];environ]]
.APART
.GROUP
%1where:%*
apply <= λ[[fn;args,environ]
\[isfunname[fn] → ....
\ islambda[fn] → eval[body[fn];newenviron[vars[fn];args;environ]]
\ isclosure[fn] → apply[func%41%*[fn];args;evn[fn]]
\ .... ..... ]]
.APART
.END
Now for some specific emamples.
In particular, most implementations of LISP include a very useful class
of ⊗→mapping functions↔←.
.BEGIN INDENT 0,10;
⊗→%3maplist%*↔← is a function of two arguments, a list, %3l%*, and a functional
argument, %3fn%*. %3maplist%* applies the function %3fn%* (of one argument)
to the list %3l%* and its %3cdr%*s until %3l%* is reduced to %3NIL%*.
The value of %3maplist%* is the list of the values returned by %3fn%*.
Here's a definition of %3maplist%*:
.END
.GROUP;
←%3maplist <= λ[[fn;l][null[l] → NIL; T → cons[fn[l];maplist[fn;cdr[l]]]]]%*.
Thus:
%3←maplist[REVERSE;(A B C D)] = ((D C B A)(D C B)(D C)(D))%*.
.APART;
.BEGIN INDENT 0,10;
⊗→%3mapcar%*↔← is a similar function, applying %3fn%* not to %3l%* but the
%3car%* of %3l%*. Thus:
.END
.GROUP
.P34:
←%3mapcar <= λ[[fn;l][null[l] → NIL; T → cons[fn[car[l]];mapcar[fn;cdr[l]]]]].%*
and an example:
←%3mapcar[(LAMBDA(X)(CONS X NIL));(A B C D)] = ((A)(B)(C)(D)).%*
.APART
.CENT(Problems)
I. What changes should be made to the LISP syntax equations to
allow functional arguments?
II. Use %3foo%* on {yon(P81)} to define a function which computes factorial without
using %3label%* or explicit calls on the evaluator.
III. Extend %3eval%* and friends to functional arguments.
.GROUP;
.P99:
IV. An interesting use of functional arguments involves ⊗→self-applicative functions↔←.
An application of a function %3f%* in a context %3f[...,f,...]%* is an instance
of self application ⊗↓provided the designated argument position is a functional
argument←. Self-applicative functions can be used to define recursive
functions in such a way that the definition is not %2statically%* self-referential,
but is %2dynamically%* re-entrant.
For example here is our canonical example, written using self-applicative functions:
.APART
.BEGIN CENTER;SELECT 3;GROUP;
fact <= λ[[n]f[function[f]; n]]
f <= λ[[g;n][n=0 → 1; T → *[n; g[g; n-1]] ]]
.END
Use Weizenbaum's environments to show the execution of %3fact[2]%*.
V. To see why %3QUOTE%* is not sufficient, evaluate the following:
****FINISH***
.BEGIN CENTERIT;
←%3tester[(A#(B)#(C));(LAMBDA()(BAZ#(QUOTE#A))]%*
.END
.BEGIN TABIT2(10,29);GROUP;
with:
%3\tester <= λ[[l;fn]\[null[l] → NIL;
\\ atom[l] → fn[ ];
\\ T → tester[car[l];(LAMBDA()(TESTER(CDR L) FN))]]]%*
and then with:
%3\tester <= λ[[l;fn]\[null[l] → NIL;
\\ atom[l] → fn[ ];
\\ T → tester[car[l];function[λ[[]tester[cdr[l];fn]]]]]%*.
.END
.END
.SS(special forms,special form,P8:)
We have remarked that the evaluation scheme for LISP functions is
call-by-value and, for functions with multiple arguments, left-to-right
evaluation of arguments. We have also seen, in %3QUOTE%* and %3COND%*,
that not all forms to be evaluated in LISP fall within this category.
We have already noted on {yon(P44)} that %3QUOTE%* and %3COND%* are
%2not%* translates of functions. Clearly we don't evaluate the arguments to
%3(QUOTE ...)%*; indeed the purpose of %3QUOTE%* was to %2stop%* evaluation.
Also the `arguments' to %3COND%* are handled differently; their evaluation was
handled by %3evcond%*.
We therefore have called %3QUOTE%* and %3COND%* %2special forms%*.
We would like to discuss special forms as a generally useful technique.
Consider the predicates, ⊗→%3and%*↔← and ⊗→%3or%*↔←. We might wish to define
%3and%* to be a binary predicate such that %3and%* is true just in case
%2both%* arguments evaluate to %3T%*; and define %3or%* to be binary
and false just in case both arguments evaluate to %3NIL%*.
Notice two points. First, there is really no reason to restrict these predicates
to be %2binary%*. Replacing the words "binary" by "n-ary" and "both" by "all"
in the above description has the desired effect.
Second, if we evaluate the arguments to these predicates in some order,
say left-to-right, then we could immediately determine that %3and%*
is false as soon as we come across an argument which
evaluates to %3NIL%*; similarly a call on %3or%* for an arbitrary number
of arguments can be terminated as soon as we evaluate an argument giving
value %3T%*.
But if we insist that %3and%* and %3or%* are %2functions%* we can
take advantage of neither of these observations. Functions have a fixed
number of arguments, all of which are evaluated. The solution should be
clear: define %3and%* and %3or%* as special forms and handle
the evaluation ourselves. Presently, the
only way to handle special forms is to make explicit modifications
to %3eval%*. This is not terribly difficult (or desirable). When
we see a more realistic version of %3eval%* and Co. in {yonss(P30)}, we will have
a simple way to add such forms. See also {yon(P54)}.
Recognizers for the predicates must be added to %3eval%*:
.BEGIN CENTERIT;SELECT 3;GROUP;
←isand[e] → evand[args[e];environ];
←isor[e] → evor[args[e];environ];
←.....%1 where:
.END
.BEGIN SELECT 3;TABIT1(16);GROUP;
.P53:
evand <= λ[[l;a]\[null[l]→ T;
\ eval[first[l];a] → evand[rest[l];a];
\ T → NIL] ]
evor <= λ[[l;a]\[null[l] → NIL;
\ eval[first[l];a] → T;
\ T → evor[rest[l];a]] ]
.END
Notice⊗↓
First notice that the "abstract" version presented here is a bit fradulent.
%3evand%* and %3evor%* "know" that the arguments are presented as a sequence.
Indeed, this deciet has been consistently practiced throughout
our description of %3eval%*.←
the explicit calls on %3eval%*. This is expensive, but cannot be helped.
Later we will show a less costly way to handle those "non-functions" which
only have an indefinite number of arguments, all of which are
to be evaluated (see {yonss(P18)} on macros).
.CENT(Problems)
I What is the difference between a special form and call-by-name? Can call-by-name
be done in LISP (without redefining %3eval%*)?
.P71:
II %3select%* is a special form to be called as:
%3select[q;q%41%*;e%41%*;#...#;q%4n%*;e%4n%*;e]%1 and to be evaluated as follows:
%3q%* is evaluated; the %3q%4i%1's are evaluated from left to right until
one is found with the value of %3q%*. The value of %3select%* is the value
of the corresponding %3e%4i%1. If no such %3q%4i%1 is found the value of
%3select%* is the value of %3e%1. %3select%* is a precursor of the
%2⊗→case statement↔←%*. See {yon(P70)}.
Add a recognizer to %3eval%* to handle %3select%* and write a function to
perform the evaluation of %3select%*.
.SS(The %3prog%*-feature,,P37:)
.TURN ON "←";
%1
Recursion seems a bit supernatural, but it is legal and mechanizable.
There is another similar ⊗→bind↔←ing process occurring in LISP. It is
connected with an iterative style of LISP programming called the
⊗→%3prog%*↔←-feature.
First a general disclaimer: Some pure ("For my next trick I'll walk
on the water") LISP programmers feel that there is something slightly
obscene about writing iterative style programs. This isn't quite
true, but there are some good reasons for emphasizing recursion.
%21.%* Anyone can write an iterative scheme. Recursion is a powerful
tool and very possibly a new programming technique
for you. You should exercise your skill and resort to the %3prog%*
as a last resort.
%22.%* Two of the usual trappings of iteration are %2labels%* and %2go-to%*'s.
These are truly tools of the devil. In recent years several studies
by reasonable men have shown that algorithms which resort to labels
and gotos tend to be harder to read, harder to modify, sloppy in their
analysis of the process being coded, and generally ugly. The label
and goto hack invites patching over poor analysis instead of
reanalyzing the problem.
%23.%* With the control of the loop structure (either recursion or some
kind of controlled iteration, e.g., a FOR or WHILE statement) in the
hands of the language rather than in the hands of the programmer, the
static text and the dynamic flow of the execution have a parallel
relationship. This has had a beneficial effect for studies
investigating the provability of properties of programs.
Now that this has been said, here's our discussion of %3prog%*s.
Many algorithms present themselves more naturally as iterative
schemes. Recall the recursive computation of the length of a list given
on {yon(P19)}. %3length%* seems inordinately complex; our sympathies
lie more with %3length%41%1. Even this is not as straightforward as you would
expect for such a simple calculation. Rather, consider the following:
%21.%* Set a pointer to the given list. Set a counter to zero.
%22.%* If the list is empty, return as value of the computation, the
current value in the counter.
%23.%* Otherwise, increment the counter by one.
%24.%* Set the pointer to the cdr of the list.
%25.%* Go to line 2.
The new ingredients here are:
%21.%* An ⊗→assignment↔← statement: "set a ...".
%22.%* Access to some new cells: the pointer, the counter.
%23.%* Sequencing (albeit usually implied) between statements: line %21%*, then line %22%*...
%24.%* Gotos and labels.
%25.%* An explicit exit from the procedure: line %22%*.
Here is the LISP %3prog%* version of the length function:
.BEGIN TABIT2(15,17);SELECT 3;GROUP;TURN OFF "←";
.P45:
⊗→length↔← <= λ[[x]prog[[l;c]
\\l ← x;
\\c ← 0;
\a\[null[l] → return[c]];
\\l ← cdr[l];
\\c ← c+1;
\\go[a]] ]
.END
A few points should be made: The ⊗→%3prog%*-variables↔←, %3l%* and %3c%1, are ⊗→local variable↔←s.
That is, they only have meaning within this definition of %3length%*. If they
appeared in some program which called %3length%*, then the right thing
would happen; the old values would be saved (like λ-bindings) and then
restored after the call on %3length%* has been completed. Among other things,
this allows %3prog%*s to be used recursively.
Though assignment statements are normally executed for their effect on the
environment -- they have side-effects, assignments in LISP also have a value.
The value of an assignment is the value of the right-hand-side.
Conditional expressions have a slightly different effect inside %3prog%*s. If
none of the predicates in the conditional are true, then the statement following
the conditional is executed.
.P83:
Labels are clear; they are identifiers. Labels are local, that is must be found
within the body of the current %3prog%*. Labels may conflict with the
λ-variables or %3prog%*-variables; the evaluator for %3prog%*s can resolve the
conflicts by context.
⊗→%3go%*↔← is a little more complicated. %3go%* is a special form. If the argument
to %3go%* is %2atomic%* then it is interpreted as a (local) label; otherwise, the argument
is %2evaluated%* and the result of the evaluation is interpreted as a label.
This results in a useful programming trick. Let %3l%* be a list of dotted pairs,
each of the form, %3(%* object%4i%* . label%4i%3)%1. At each label%4i%* we
begin a piece of program to be executed when object%4i%* has been recognized.
Then the construct:
.P25:
←%3go[cdr[assoc[x;l]]]%* (*1*),
can be used to "dispatch" to the appropriate code when %3x%* is one of the
object%4i%*. This is an instance of %2⊗→table-driven↔←%* programming.
This programming trick shows "go-to" programming in its most pervasive form.
The blocks of code dispatched to can be distributed throughout the body of the
%3prog%*. Each block of code will usually be followed by a %3go%* back to
the code involving equation *1* (above). In fact the argument %3l%* in *1*
may be %2global%* to the %3prog%*-body.
The general effect is to make a %3prog%* which is very difficult to understand.
The LISP %3select%* ({yon(P71)}) will handle many of the possible applications
of this coding trick and result in a more readable program. The case-statement ({yon(P70)})
present in some other languages is also a better means of handling this problem.
The ⊗→%3return%*↔← statement evaluates its argument, and returns that value as
the value of the %3prog%*.
When a %3prog%* is entered the %3prog%*- (local) variables are initialized to %3NIL%*.
The body of the %3prog%* is a sequence of statements and labels. Statements are
executed sequentially unless a %3go%* or %3return%* is evaluated.
If a %3prog%* runs out of statements then %3NIL%* is returned.
Returning from a %3prog%* unbinds the local variables.
Now to the problem of translating %3prog%*s into a s-expression representation.
We need be a little careful. First notice that %3prog%* is a %2⊗→special form↔←%*
(like %3COND%* and %3QUOTE%*). The construct:
←%3prog[[l;c]....]%* will be translated to:
←%3(PROG(L C) ...)%*.
But %3PROG%* is not the translate of a function
any more than %3(QUOTE ...)%* or %3(COND ...)%* is.
So the body of the %3prog%* must be handled specially by a
new piece of the evaluator.
.TURN OFF "←";
Similarly we must be careful about the interpretation of ←. First,
we will write %3x ← y%* in prefix form: %3←[x;y]%*. Now, using our usual LISP
technique we might map this to:
.BEGIN CENTER
%3(SET X Y).%* Is ← or ⊗→%3SET%*↔← a function in the usual LISP sense?
.END
Not likely; for if %3x%* and %3y%* have values %32%* and %33%*, for example, then the
call-by-value interpretation of %3←[x;y]%* would say %3←[2;3]%*. This was not our
intention, hopefully. What do we want? We want to evaluate the second argument
to ← while stopping the evaluation of the first argument. But LISP does
have a device for stopping evaluation: ⊗→%3QUOTE%*↔←. So we can define %3SET%* as a normal
LISP function, provided we
.BEGIN CENTER
translate %3x ← y%* as %3(SET (QUOTE X) Y)%*.
.END
.TURN ON "←";
For example, look at the evaluation of %3(SET (QUOTE X)(PLUS X 1)).%*
Assume the current value of %3X%* is %32.
SET%* is a function; evaluate the arguments from left to right. The
value of %3(QUOTE X)%* is %3X%*; the value of %3(PLUS X 1)%* is %33%*; assign %33%* to %3X%*.
Question: what does %3(SET Z (PLUS X 1))%* mean? Well if the current value of
variable %3z%* (represented by %3Z%*) is an identifier (non-numeric atom), then
%3(SET Z (PLUS X 1))%* makes sense. Assume the current value of %3Z%* is %3A%*, then
the effect of the %3SET%* statement is to assign the value %33%* to %3A%*.
Normally when you are making assignments, you want to assign to a %2name%* and
not a %2value%*; thus you will be using the form
←%3(SET (QUOTE ...) ...).%*
As a convenience an abbreviation, ⊗→%3SETQ%*↔←, has been made available:
←%3(SETQ ... ... )%* means %3 (SET (QUOTE ...) ...).%*
Again note that %3SETQ%* is not (the translate of) a function. It may be
defined as a special form or consider as a notational convenience like %3list%*.
Here is a translation of the body of the %3prog%* version of %3length:%*
.GROUP
%3
.BEGIN TABIT3(10,17,20);
\(LAMBDA(X)
\\(PROG(L C)
\\\(SETQ L X)
\\\(SETQ C 0)
\\A\(COND ((NULL L)(RETURN C)))
\\\(SETQ L(CDR L))
\\\(SETQ C (ADD1 C))
\\\(GO A) ))
.END
.APART
%1
Now that assignment statements are out in the open let's reexamine "<=".
We already know ({yon(P89)}) that "<=" does more than simply associate the
right hand side with a symbol table entry of the left hand side; it must also
associate an environment with the function body, and this environment is to be
used for accessing global variables. This operation of associating environments
is called forming the %2⊗→closure↔←%*. We thus might be tempted to say:
.BEGIN CENTER;SELECT 3;TURN OFF "←";
f <= λ[[ ... ] ...] %1is%* f ← closure[λ[[ ...] ...] ].
.END
where %3closure[g]%* is to give as value a representation of the function %3g%*
associated with the %2name%* of the current environment
⊗↓We may %2not%* associate the current %2value%* of the
environment (i.e. symbol table). Why?←.
Alas, this implementation is still not sufficient as we will see in {yonss(P90)}.
.REQUIRE "PROB7.PUB" SOURCE_FILE;
.SS(In retrospect,,P90:)
We will begin with a sketch of the LISP evaluator as it would now appear:
basic %3eval%* plus the additional artifacts for %3label, function%*, and %3prog%*.
This evaluation process is very important and, though it is perhaps new material,
should appear quite intuitive.
%3eval%* and friends are not to be memorized. If
you cannot write functions equivalent to %3eval%*, then you have not understood
LISP evaluation.
Finally, we will examine some of the weaknesses present in LISP.
There are alternatives to some of the LISP techniques and there are some things
which, in retrospect, LISP could have done better.
First, the basic evaluator.
There are two arguments to %3eval%*: a %2form%* ⊗↓throughout this section we
will say "form", "variable", "λ-expression", etc. rather than "an S-expression
representation of a" ... "form", "variable", "λ-expression", etc. No
confusion should result, but remember that we %2are%* speaking imprecisely.←, that
is an expression which can be evaluated; and second, an association list or
%2symbol table%*. If the form is a number, the atom %3T%* or %3NIL%*, return that
form. If the form is a variable, find the value of the variable in the current
table or environment. If the form is a (non numeric) S-expression constant, return
that constant. If the form is a conditional expression, then evaluate it
according to the semantics of conditional expressions. If the form is a
%3prog%*, evaluate the body of the %3prog%* after binding the local %3prog%* variables
to %3NIL%*⊗↓Perhaps you can now see why quoted expressions, conditional expressions,
and %3prog%*s are called %2special forms%*.←.
The form might also be a functional argument. In this case evaluation consists of
forming the ⊗→closure↔← of the function, i.e., associating the current environment
with the function. In LISP this is done with the %3FUNARG%* device.
Any other form seen by %3eval%* is assumed to be a function followed by arguments.
The arguments are evaluated from left-to-right and the function is then applied
to these arguments.
The part of the evaluator which handles function application is called %3apply%*.
%3apply%* takes three arguments: a function, a list of evaluated arguments, and
the current symbol table. If the function is one of the five LISP primitives
then the appropriate action is carried out. If the function is a λ-expression
then bind the formal parameters (the λ-variables) to the evaluated arguments and
evaluate the body of the function. The function might also be the result of a
functional argument binding; in this case apply the function to the arguments
in the saved environment rather than in the current environment.
We might also be applying the label operator. All we need do here is apply the
function definition to the arguments in the current context augmented by the
binding of the function name to its definition.
We have saved what seems to be the simplest for last. That is, the function
has a name.
What we do is look up that name in the current environment.
To look something up means to find its value.
Currently we expect that value to be a λ-expression, which is then applied.
However, since function names are just variables, there is no reason that the
value of a function name could not be a simple value, say an atom, and
%2that%* value
applied to the arguments, etc. Indeed examination of %3apply%* on {yon(P69)}
will show that %3apply[X;#((A B))#;#((X#.#CAR)#...#)]%* %2will%* be handled correctly.
The obvious extension of this idea is to allow a %2⊗→computed function↔←%*. That
is, if the function passed to apply is not recognized as one of the preceding
cases, then evaluate the expresssion until it is recognized. Thus
we will allow such forms as:
.BEGIN CENTERIT;SELECT 3;
←((CAR#(QUOTE#(CAR#(A#.#B))))#(QUOTE#(A#.#B)))
.END
What conceptual difficulties are present in LISP evaluation?
One of the more important defects in LISP is its inadequate handling of function
valued variables, functional arguments being a particular case which LISP does
attend to correctly.
LISP was the first language to handle functional arguments so it is not too suprising
that all is not quite right.
The %3FUNARG%* device is sufficient for simple uses of functional arguments and
closures. However, we should like to return functions and closures as %2values%*.
Returning ⊗→open function↔←s is easy; we can simple %3cons%*-up λ-expressions.
Returning closures is more difficult. So perhaps we should finally lay "<=" to
rest. As you might have expected, difficulties occur when we examine recursive
definitions.
.P94:
Consider the canonical example:
.BEGIN CENTERIT;SELECT 3;
←fact <= λ[[x][x=0 → 1; T → *[x;fact[x-1]]]]
.END
First, we attempted to implement this as:
.BEGIN CENTER;SELECT 3;TURN OFF "←";
fact ← closure[λ[[x] ... fact[x-1] ..]
.END
we must use the %2name%* of the environment current at closure-time rather
than the value, since at the time we form the closure the name %3fact%* is
a free variable. Any value associated with %3fact%* at this time would be the
wrong one ⊗↓%2One%1 value would suffice; what is it?←. For example:
.BEGIN TABIT3(30,34,38);GROUP;TURN OFF "←";
\\E%4i%*
\\|
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3foo%*
.APART
.GROUP
Then executing %3fact ← closure[ ... ]%* should give:
\\E%4i%*
\\|
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
.APART
.GROUP
rather than:
\\E%4i%*
\\|
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : fact|foo%*.
.END
You should reflect on the current development before reading further.
There are problems however if we just associate the name of the environment
in the closure operation.
For example, consider the following sequence:
.BEGIN TABIT3(30,34,38);GROUP;
An initial environment:
\\E%4i%*
\\|
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
.apart;
.GROUP;
Now execute %3foo <= fact%*, giving:
\\E%4i%*
\\|
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
\%3foo%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
.END
.BEGIN TURN ON "#";
This state should start worrying you; the "intent" of %3foo#<=#fact%*
was to make %3foo%* synomymous with %3fact%*. That clearly is not the case
though the right thing happens if we were now to evaluate an expression
involving %3foo%*. The problem is that it happens for the wrong reason: the occurrence
of %3fact%* in the body of %3foo%* will find the right definition of %3fact%*.
One more step will lead to disaster: %3fact#<=#loser%*.
.END
Now we have really lost. Though it is perfectly reasonable to redefine %3fact%*
--it is only a name-- our intent was clearly to keep %3foo%* as a realization
of the factorial function. This intent has not been maintained ⊗↓%1This example
was shown to the author by D. B. Anderson.←. So at least in the presence of
recursive definitions we really must be careful.
The %2real%* intent of the recursive definition of %3fact%* was to define a
function to effect the computation of factorial and then to %2name%* that
function %3fact%*.
Or, put another way, the effect of
.BEGIN CENTER;
%3fact%* <= %3λ[[x] ...fact[x-1]]%1 is quite different from:
%3foo%* <= %3λ[[x] ...fact[x-1]].
.END
Clearly we failed to handle this general problem, though
LISP does handle its %3label%* subset correctly.
Let's see what's really going on.
Perhaps an easier avenue lies in looking first at assignments to %2simple%*
variables rather than functional variables. It is clear how the environment
should change during the execution of a sequence say:
.BEGIN TABIT1(30);TURN OFF "←";SELECT 3;GROUP;
\x ← 3
\y ← x
\x ← 4
.END
Let's try something slightly more complicated:
.BEGIN TABIT1(30);TURN OFF "←";SELECT 3;GROUP;
\x ← 1
\x ← x%82%* - 6
.END
Here we simply assign %31%* to %3x%*; then while we are evaluating the right
hand side of the next statement, we look up the current value of %3x%*,
perform the appropriate computations, and finally assign the value %3-5%*
to %3x%*. Compare %2this%* to the %3fact%* definition; there we made a point
of not "evaluating" %3fact%* on the right hand side of "<=". What %2is%* happening?
.P109:
.BEGIN TURN ON "#";TURN OFF "←";
Notice that %2after%* an assignment like %3y#←#x%* has been executed, then
equality holds between the left-hand and right-hand quantities ⊗↓Indeed, a
logic of programs, due to C.A.R. Hoare, exploits this fact in interpreting
assignment.←.
Let's look more closely at the relationship between "←" and "=".
Consider %3x#←#x%82%*#-#6%1. After the assignment is made, equality
does %2not%* hold between left- and right-hand sides. We must be
careful.
Consider %3x#=#x%82%*#-#6%1.
Interpreting this expression as an equation ⊗↓%1Not as an expression
whose value is true or false depending on the current value of %3x%*← we find
two solutions: let %3x%* have value %3-2%* or %33%*.
Now if we examine our "definition" of %3fact%* in %2this%* light, interpreting
"<=" as being related to "=" rather than "←", then we are faced with an equation
to be solved. Only now the form of the solution is a %2function%* which satisfies
the equation. There are frequently many solutions; there may be no solutions.
In the our case there is at least one solution: the usual factorial function.
So what we %2should%* write is something more like:
.BEGIN CENTER;SELECT 3;
fact ← %1a solution to the equation%*: f = λ[[x][x=0 → 1; T → *[x;f[x-1]]]];
.END
.END
Questions of when solutions exist, how many, and which are the "best" solutions are too
technical for this discussion, though we will say a bit more in {yonss(P85)}.
This discussion should make clear the necessity of distinguishing between
assignment and equality; fortunately, many programming languages use notations
which reinforce these differences.
.CENT(Problems);
I Write complete versions of %3eval%* and %3apply%*.
II The example of this section which points out the difficulties of closures
is not described in LISP. Can you write a pure LISP (i.e., without %3prog%*s)
program which will also exemplify this difficulty?
.SS(Towards a Mathematical Semantics,,P85:)
In {yonss(P15)} we informally introduced some ideas about proving properties
of programs. We would now like to expand on this idea of introducing
mathematical rigor into the discussion of programming languages. Though firm
technical basis can be established for the following discussion, we
wish to proceed at an intuitive level and hopefully arouse curiosity
without damaging the underlying theory.
First, why worry about foundational and theoretical work at all? Programming,
it is said, is an art and art needs no formalizing. Indeed, but there is some
science in Computer Science and %2that%* part can be analyzed.
We have borrowed heavily (but informally) from mathematics and logic; we should
at least see how much of our discussion can stand more formal analysis. We
have used the language of functions and functional composition, but have
noted that not all LISP expressions are to be given a usual mathematical connotation.
In particular, conditional expressions are %2not%* to be interpreted as functional
application. In mathematics, a function is a mapping or set of ordered pairs;
composition simply denotes a %2new%* mapping or set of ordered pairs. Nothing
is said about how to calculate members of the set of pairs, or indeed, whether
such a set can be effectively (mechanically) given. Can we give an interpretation
to LISP expressions which involves nothing more than the mathematical
description of function but preserves our LISP-ish intent?
Most of the description of LISP which we have given so far is classified as ⊗→operational↔←.
That means our informal description of LISP and our later description of the LISP
interpreter are couched in terms of "how does it work (operate)". Indeed
the whole purpose of %3eval%* was to describe explicitly what is to happen
when a LISP expression is to be evaluated. We have seen ({yon(P84)}) that discussion
of evaluation schemes is non-trivial; and that order of evaluation can effect the
outcome ({yon(P17)}).
.BEGIN TURN ON "#";
.P91:
However, many times the order of evaluation is immaterial
⊗↓One difficulty with the operational approach is that it (frequently)
specifies too much: C. Wadsworth.←.
We saw on {yon(P93)} that %3eval%* will perform without complaint when
given a form %3f[#...#]%* supplied with too many arguments.
How much of %3eval%* is "really" LISP and how much is "really" implementation.
On one hand we have said that the meaning of a LISP expression %2is%*
(by#definition) what %3eval%* will do to it. On the other hand
it is quite reasonable to claim %3eval%* is simply %2an implementation%*.
There are certainly other implementations; i.e, other functions %3eval%4i%1
which have the same input-output behavior as our %3eval%*.
The position here is not that %3eval%* is wrong in giving
values to things like %3cons[A;B;C]%*, but rather: just what is it that
%3eval%* implements?
This other way of looking at meaning in programming languages is exemplified by
⊗→denotational↔← or mathematical semantics.
.P96:
This perspective springs from a common mathematical, philosophical, or logical
device of distinguishing between a %2representation%* for an object, and the
object itself. The most usual guise is the numeral-number distinction.
Numerals are notations (syntax) for talking about %2numbers%* (semantics).
thus the Arabic %2numerals%* %32, 02%*, the Roman numeral %dII%*,
and the Binary notation %310%*, all %2denote%* or represent
the %2number%* two. In LISP, %3(A#B), (A#.(B)), (A,B)%* and %3(A#.(B#.#NIL))%*
all are notations for the same symbolic expression, thought of as an abstract object.
We could say that a LISP form %2denotes%* an sexpression (or is undefined) just
as we say in mathematics that 2+2 denotes 4 or 1/0 is undefined.
Thus %3car[cdr[(A#B)]]%* denotes %3B%* ⊗↓Or more precisely, denotes a symbolic
expression which we represent by %3B%*.←.
The scheme which we use to evaluate the expression
is irrelevant; there is some object which our expression denotes and the process
which we use to discover that object is of no concern.
Similarly, we will say that
the denotational counterpart of a LISP function or %3prog%* is just a
(mathematical) function or mapping defined over our abstract domain.
Before proceeding, discretion dictates the introduction of some conventions
to distinguish notation from %2de%*notation.
.BEGIN GROUP;
We will continue to use italics:
.BEGIN CENTER;
(%3A, B, ..., x, ... car, ...(A . B) %*) as notation in LISP expressions.
.END
Gothic bold-face:
.BEGIN CENTER;
(%dA, B, ..., x, ...car, ...(A . B)%*) will represent denotations.
.END
.END
Thus %3A%* is notation for %dA%*;
%3car[cdr[(A#B)]]%* denotes %dB%*; the mapping, %dcar%* is the denotation
of the LISP function %3car%*.
.BEGIN TURN OFF "⊗";
The operation of composition of LISP functions denotes mathematical composition;
thus in LISP, %3car[cdr[(A#B)]]%* means apply the function %3cdr%* to the
argument %3(A#B)%* getting %3(B)%*; apply the function %3car%* to %3(B)%*
getting %3B%*. Mathematically speaking, we have a mapping, %dcar%2⊗%*cdr%1
which is a composition of the %dcar%* and %dcdr%* mappings; the ordered
pair %d<(A#B)#,#B>%* is in the graph of this composed mapping.
%dcar%2⊗%*cdr(#(A#B)#)%1 is %dB%*.
.END
In this setting, any LISP characterization of a function is equally good;
the "efficiency" question has been abstracted
away. But notice that many important properties of real programs %2can%* be
discussed in this rarefied mathematical context;
in particular, questions of equivalence
and correctness of programs are still viable, and indeed,
more approachable.
Lest your confusion give way to dispair, we should point out that
denotational thinking %2has%* been introduced before.
When we said ({yon(P86)}) that:
.BEGIN CENTERIT;SELECT 3;
←f[a%41%*; ... a%4n%*] = eval[(F A%41%* ... A%4n%*) ...],
.END;
we are guilty of denotational thought. The left hand side of this equation
is denotational; the right hand side is operational.
This denotational-operational distinction is appropriate in a more general context.
When we are presented with someone's program and asked "what does it compute?"
we usually begin our investigation operationally, discovering "what does it %2do%*?".
⊗↓Another common manifestation of this "denotation" phenomonon is the common
programmer complaint: "It's easier to write your own than to understand
someone else's."←
Frequently by tracing its execution we can discover a concise (denotational) description
(E.g.,#"ah!#it#computes#the#square#root.").
.END
The author has already victimized you in this area of denotation and operation.
When %3great mother%* was presented it was given as an operational exercise,
with the primary intent to introduce the LISP evaluation process without
involving the stigma of complicated names. Forms involving %3great mother%* were
evaluated perhaps without understanding the denotation, but if asked "what does
%3great mother%* do?" you would be hard pressed to given a comprehensible
purely operational definition. However you might have discovered the true insidious
nature of %3great mother%* yourself; then it would be relatively easy to describe
its (her) behavior. Indeed, once the denotation of %3great mother%* has been discovered
questions like "What is the value of %3tgmoaf[(CAR (QUOTE (A . B)))]%*? " are usually
answered by using the denotation of %3tgmoaf%*: "what is the value of %3car[(A . B)]%*?"
⊗↓The question of how one gives a convincing argument that the successor of %3tgmoaf%*,
(i.e. %3eval%*), %2really does%1 faithfully represent LISP evaluation is the
subject of a recent dissertation by M.J.C. Gordon.←
Finally, for the more practically-minded: the care required in defining a
denotational model for LISP will pay dividends in motivating our
extension to LISP in {yonsec(P87)}.
Let us begin to relate these intuitions to our discussion of
LISP ⊗↓%1This section owes a great deal to M.J.C. Gordon's thesis.
However our presentation is much like that of a person who writes
down a set of axioms, declares that they characterize a particular theory,
but gives no consistency or completeness proofs. Gordon's thesis
contains the necessary substantiation for our light-fingered discussion.←.
We will parallel our development of interpreters for LISP since each subset,
%3tgmoaf, tgmoafr%*, and %3eval%*,
will also introduce new problems for our mathematical semantics.
Our first LISP subset considers functions, compostion, and constants.
Constants will be elements of our domain of interpretation.
Clearly, our domain will include
the S-expressions since %2most%* LISP expressions %2denote%* Sexprs. However, we
wish to include more; many of our LISP functions are partial functions.
It is convenient to be able to talk about the undefined value; in other words we
wish to extend our partial functions on sexprs to be %2total%* functions on
(denotations of) sexprs or "undefined". Our domain
must then include a denotation for "undefined". We will use the symbol %aU%*.
We shall call this extended domain %aS%* (%3≡%*%d<sexpr>%a∪%aU%1)
⊗↓Recall that %d<sexpr>%*'s are simply the denotations of elements in <sexpr>.
I.e.,<sexpr>'s are specific (syntactic) representations; %d<sexpr>%*'s
are abstract objects. Compare the numeral-number discussion on {yon(P96)}.
We could simply muddle the distinction here, but is worthwhile to make a clean
break.←.
Before we can talk very precisely about the properties of LISP functions
we must give more careful study to the nature of domains.
Our simplest domain is %d<atom>%*.
It's intuitive structure is quite simple, basically just a set of atoms
or names with no inherent relationships among the elements.
But what kind on an animal is %d<sexpr>%*? It's a set of elements, but many
elements are related. Can we say any more about the characteristics of
%d<sexpr>%*? In our discussion of %d<sexpr>%* beginning on {yon(P47)}
we tried to make it clear that there is more than syntax involved.
Couching that argument in mathematical terminology we could say that
for %ds%41%1 and %ds%42%1 in %d<sexpr>%* then the essence of "dotted pair"
is contained in the concept of the set-theoretic ordered pair,
<%ds%41%1,%ds%42%1>. Thus the "meaning" of the set of dotted pairs is
captured by Cartesian product, %d<sexpr>#%ax%*#<sexpr>%1.
Let's continue the analysis of:
.BEGIN CENTERIT;
←<sexpr> ::= <atom> | (<sexpr> . <sexpr>)
.END
We are trying to interpret this BNF equation as a definition of the
domain %d<sexpr>%*. Reasonalbe interpretations of "::=" and "|" appear to
be equality and set-theoretic union, respectively. This results in the
equation:
.BEGIN CENTERIT;SELECT d;
←<sepxr> = <atom> %a∪%* <sexpr> %ax%* <sexpr>
.END
What does this equation mean? It's just like an equation in algebra, and
as such,
it may or may not have solutions ⊗↓Recall the discussion on {yon(P109)}.←.
Luckily for us, this "domain equation" has a solution: the s-exprs
we all know and love.
There is a natural mapping of BNF equations onto such "domain equations",
and the solutions to the domain equations are sets satisfying
the abstract essence of the BNF. The question of existence of solutions,
and indeed the methods involved in obtaining solutions to such equations,
will not be discussed here. The recent studies by D. Scott and C. Strachey
analyze these problems. Most of the foundational work is too advanced
for our discussion.
However, we will persue one very important interpretation of a set of BNF
equations which will demonstrate some of the subtlity
present in Scott's methods.
Consider the following BNF:
.BEGIN CENTERIT;
←<e> ::= <v> | λ<v>.<e> | (<e> <e>)
.END
These equations comprise a syntax description of the λ-calculus, similar
to that given in {yonss(P49)}.
We would like to describe the natural denotations of these equations in a
style similar to that used for <sexpr>'s.
The denotations of the expressions, <e>,
of applications, (<e> <e>), and of the variables,
<v>, are just constants of the language; call this domain %dC%*.
What should be the denotation of "λ<v><e>"? A reasonable choice,
consistent with our intuitions of the λ-calculus, is to
take the set of functions from %dC%* to %dC%*. Write that set as
%dC#→#C%*. Then our domain equation is expressed:
.BEGIN CENTERIT;SELECT d;
←C = C→C
.END
What kind of solutions does this equation have? The answer is easy. It has
absolutely %2no%* interesting solutions! A simple counting argument will establish this.
Unless the domain %dC%* is absolutely trivial, then the number of functions
in %dC#→#C%* is greater than the number of elements in %dC%*.
Does this say that there are no models of the λ-calculus?
We hope not. What it %2should%* say is that our interpretation of "%d→%*"
is too generous. What is needed is an interpretation of functionality
which will allow a solution to the above domain equation; indeed it
should allow a natural interpretation such that the properties which
we expect functions to posses are, in fact, true in the model.
Scott gave one such
interpretation of "%d→%*" delimiting what he calls
the class of "continuous functions.
We will assume without proof that the denotations which we ascribe to
LISP functions in the remainder of this section are in fact continuous.
Then, for example, the
mathematical counterpart to the LISP function %3car%* is the mapping %dcar%* from
%aS%* to %aS%* defined as follows:
.BEGIN TABIT2(10,20);GROUP
\%dcar:%aS%1→ %*S%1
\\ %1| is %aU%* if %dt%* is atomic
\%dcar(t)\%1< %dt%41%1 if %dt%* is %d(t%41%* . t%42%*)
\\ %1| is %aU%* if %dt%* is %aU%*.
.END
Similar strategy suffices to give denotations for the other primitive LISP functions
and predicates. For example:
.BEGIN TABIT2(10,20);GROUP
\%datom:%aS%1→ %*S%1
\\ %1| is %dNIL%* if %dt%* is not atomic.
\%datom(t)\%1< is %dT%* if %dt%* is atomic.
\\ %1| is %aU%* if %dt%* is %aU%*.
.END
.BEGIN TURN OFF "{","}";
Notice that %datom%* maps onto a subset of %aS%* rather than a set like {true, false,%aU%*} of
truth values. This behavior is in the spirit of LISP. LISP has already decided to
map truth-values onto the sexpressions %3T%* and %3NIL%*.
.END
Now, corresponding to %3tgmoaf%*, we will have a function, %9D%4tg%1, mapping expressions
onto their denotations. Thus:
.BEGIN TABIT2(30,35);GROUP;TURN ON "#";
\%9D%4tg%1:\<form> => %aS%*.###⊗↓%1Note the difference between "=>" and "→".
The former denotes a map from LISP constructions into denotations;
the latter a map between denotations.←
\\ %3car%1 => %dcar%*
\\ etc. for %3cdr, cons, eq,%1 and%* atom%1.
.END
.BEGIN TURN OFF "{","}";
Before giving the details of %9D%4tg%1, we need to introduce some notation for
naming elements of the sets <sexpr> and <form>. Let %as%* range over <sexpr>
and %af%* range over <form>, then using "{" and "}" to enclose LISP constructs
we can write:
.BEGIN centerit;GROUP;
←%9D%4tg%1{%as%*} = %ds%*
←%9D%4tg%1{%3car[%af%*]%1} = %dcar%*(%9D%4tg%1{%af%*})
←with similar entries for %3cdr, cons, eq, %1and %*atom%*.
.END
.END
The similarity with %3tgmoaf%* should be apparent.
.BEGIN TURN ON "#";
The structure of our denotation function, %9D%1, will obviously become more complex
as we proceed. Notice that the denotations for the LISP functions are mappings
such that if any argument is undefined then the value is undefined. That is
%df(#...,%aU%*,#...)%1 is %aU%*. Such mapping are called %2⊗→strict↔←%*.
This is as it should be: forms %3f[e%41%*,#...,#e%4n%*]%1 are undefined if
any %3e%4i%1's are undefined. As we will see, there are natural mappings which are
%2not%* strict; i.e., they can give a value other that %aU%* even when an argument
is %aU%*.
Let's now continue with the next subset of LISP, adding conditional
expressions to our discussion. As we noted on {yon(P88)}, a degree of care need
be taken if we attempt to interpret conditional expressions in terms of mappings.
First we simplify the problem slightly; it is easy to show that a general
LISP conditional can be expressed in terms of the more simple expression,
[p%41%*#→#e%41%*;#%3T%*#→#e%42%*]%1.
Now, using our extended domain, %aS%*, it %2is%* reasonable to think
of conditional expressions as function applications in the mathematical
sense ⊗↓Obviously, the order of evaluation of arguments to the conditional
expression will have been "abstracted out". But recall the comment of Wadsworth
({yon(P91)}). Indeed, the use of conditional expressions in the more
abstract representations of LISP functions frequently is such that
exactly one of the p%4i%*'s is %3T%* and all the others are %3NIL%*.
Thus in this setting, the order of evaluation of the predicates is useful
for "efficiency" but not necessary to maintain the sense of the definition.
See {yon(P101)}.←.
Consider [p%41%*#→#e%41%*;#%3T%*#→#e%42%*]%1 as denoting %dcond(p%41%*,e%41%*,e%42%*)%1
where:
.BEGIN TABIT2(10,22);GROUP
\%dcond: %aS%*x%aS%*x%aS%* → %aS%*
\\ %1| is%* y %1if%* x %1is%* %dT%*
\%dcond(x,y,z)\%1< is %dz%1, if %dx%1 is %dNIL%*.
\\ %1| is %aU%1, otherwise
.END
.END
This interpretation of conditional expressions is appropriate for LISP; other
interpretations of conditionals are possible. For example:
.BEGIN TABIT2(10,24);GROUP
\%dcond%41%*: %aS%*x%aS%*x%aS%* → %aS%*
\\ %1| is%* y %1if%* x %1is%* %dT%*
\%dcond%41%*(x,y,z)\%1< is %dz%1, if %dx%1 is %dNIL%*.
\\ %1| is %aU%1 if %dx%* is %aU%* and %dy ≠ z%*
\\ %1| is %dy%1 if %dx%* is %aU%* and %dy = z%*
.END
Notice neither %dcond%* or %dcond%41%1 are strict mappings.
Now to add (simplified) conditionals to %9D%4tg%1, yielding %9D%4tgr%1:
.BEGIN TABIT1(12);TURN OFF "{","}";FILL;
\%9D%4tgr%1{%3[%af%41%3 → %af%42%3; T → %af%43%3]%1} =
%dcond(%9D%4tgr%1{%af%41%1}%d,%9D%4tgr%1{%af%42%1}%d,%9D%4tgr%1{%af%43%1}%d)%1
.END
As with the LISP evaluators, nothing particularly novel appears until we
begin consideration of variables. What is the denotation of a variable?
As we know, the value of a LISP <variable> ({yon(P66)}) depends on the
current environment or symbol table. Denotationally, things
really don't differ much from the discussion of %3eval%*. All we need
do ⊗↓This statement is a bit too optimistic!← is give a mathematical
representation of environments.
As a reasonable first attempt we can try characterizing environments as
functions from variables to sexpressions; i.e.:
.BEGIN CENTER
%denv %1is the set of functions: <%dvariable%*> → %aS%1.
.END
.BEGIN TURN ON "#";
Indeed, this is essentially the argument used in introducing %3assoc%* ({yonss(P92)}).
Note too, that %3assoc[x;l]#=#%dl(x)%1 is another instance of a
operational-denotational relationship. We will exploit this remark in a moment.
.END
.BEGIN TURN OFF "{","}";
So, given a LISP variable, %3x%*, and a member of %denv%*, say
the function %d{<x,2>,<y,4>}%*, then
our newest %9D%* should map %3x%* onto %d2%*. This is an intuitive way of saying
that %9D%* should map a member of <variable> onto a %2function%*. This function
should map a member of %denv%* onto an element of %aS%*. Now to make things more precise.
.END
.BEGIN TABIT2(30,35);TURN OFF "→";
\%9D%*:\<variable> => [%denv%* → %aS%*]
.END
.BEGIN TURN OFF "{","}";TURN ON "#";
Thus for example: %9D%*{%3x%*}(%d{<x,2>,<y,4>}%1)#=#%d2%*.
Introducing %av%* as a meta-variable to range over <variable>,
then for %dl#%9ε%d#env%1 we have:
.CENTER;
%9D%1{%av%*}%d(l)%*#=#%dl(v)%1
.END
We should then say that the %2meaning%* or denotation of a variable is a function;
whereas the %2value%* of a variable is an element of %aS%1.
Alas, our present description of %denv%* is inadequate. %denv%* is
to represent symbol tables; such tables must include function names
and their defintions. Function names, like <variable>s, are in the class
<identifier>; so in the interest of simplicity %denv%* should map from
%d<identifier>%* to ...; to what? What are the denotations of LISP
functions? Clearly they should be mathematical functions or mappings.
.BEGIN TURN ON "#";
So letting
%aFn%* be the set of functions:#%9S%4n=0%1[%aS%8n%1#→#%aS%1],
and %aId%1 be %d<identifier>%1∪%aU%1,
then a more realistic approximation to %denv%* is:
.BEGIN CENTER
%denv%1 is the set of functions: %aId%1 → %aS%1 ∪ %aFn%1.
.END
.END
That is, an element of %denv%* is a function which maps an identifier
either onto a s-expression or onto a function from s-expressions to s-expressions.
We shall soon see that even this is inadequate.
Meanwhile, let's continue expanding %9D%*.
We shall maintain the parallels between evaluation and denotation, by giving
%9D%4e%1 and %9D%4a%1 corresponding to %3eval%* and %3apply%*.
.BEGIN TABIT2(20,26);TURN OFF "→";GROUP;
Thus: \%9D%4e%1:\<form> => [%denv%* → %aS%*] and
\%9D%4a%1:\<function> => [%denv%* → %aFn%*].
.END
We must also make consistent modifications to the previous clauses of %9D%4tgr%1 to
account for environments. For example:
.BEGIN TURN OFF "{","}";TURN ON "#";
%9D%4e%1{%as%*}(%dl%*)#=#%ds%*. That is, the value of a constant is independent of the
specific environment in which it is evaluated. The simple modification for
conditional expressions is left to the reader.
.END
Some of the more obvious properties of %9D%4a%1 hold:
.BEGIN TURN OFF "{","}";
.BEGIN CENTER;
%9D%4a%1{%3car%1}%d(l)%1 = %dcar%*
.END
.BEGIN TURN ON "{","}";
Similar equations hold for the other LISP primitive functions and predicates.
To mimic look-up of a variable used as a function name we propose: ⊗↓This is
not a sufficient characterization.←
.END
.CENTER;
%9D%4a%1{%af%*}%d(l)%* = %dl(f)%*, where %af%* %9ε %1<function>.
.END
To describe the evaluation of a function-call in LISP we must add
an equation to %9D%4e%1:
.BEGIN TURN OFF "{","}";TABIT1(15);FILL;TURN ON "#";
\%9D%4e%1{%af%*[%as%41%1,#...,%as%4n%1]}%d(l)%1#=#
%9D%4a%1{%af%1}%d(l)(%9D%4e%1{%as%41%1}%d(l)%1,#...,%9D%4e%1{%as%4n%1}%d(l))%1
.END
Clearly, before we get very far in applying functions to values
we must give a mathematical characterization of function definitions.
We will do this in five (increasingly complex) steps. First
we handle λ-notation without free variables;
next, %3label%* definitions without free variables;
then λ-notation involving free variables;
explication of recursive definitions in denotational semantics comes next; and
finally we examine recursion in the presence of free variables.
First,
what should be the denotation of %3λ[[x%41%*, ..., x%4n%*] %9x%1]
⊗↓Assuming the only free variables in %9x%* are among the %3x%4i%*'s.← in an
environment? Intuitively, it should be a function, and recalling
({yon(P93)}) that %3eval%* expects n-ary
LISP functions be supplied with at %2least%* n arguments, it should
be a function from %aS%9*%1 to %aS%* such that:
.BEGIN TURN OFF "{","}";TABIT1(15);FILL;TURN ON "#";
\%9D%4a%1{λ[[%av%41%1,#...#%av%4n%1]%as%1]}%d(l)%1#=#
%d%9λ%d(x%41%*,#...,#%dx%4n%*)%9D%4e%1{%as%1}%d(l#:#<x%41%*,%dv%41%d>,#...,#<x%4n%*,%dv%4n%d>)%1
.END
.BEGIN TURN ON "#";
where λ is the LISP λ-notation and %9λ%* is its mathematical counterpart.
%dv%4i%1 is the denotational counterpart of %av%4i%1.
In more detail:
%9λ%d(x%41%*, ... ,x%4n%*)e(x%41%*, ... ,x%4n%*) %1is a function %df%*: %aS%8n%1 → %aS%* such that:
.BEGIN TABIT1(15);GROUP;
\ | is %de(t%41%*, ... ,t%4n%*) %1if m%c≥%*n and %c∀%*i%dt%4i%1 %c≠%* %aU%1.
%df(t%41%*, ... t%4m%*) %1\<
\ | is %aU%* otherwise
.END
Also, %d(l#:#<x%41%*,%dv%41%d>,#...,#<x%4n%*,%dv%4n%d>)%1 is a modification
of %dl%* such that each %dv%4i%1 is bound to the corresponding %dx%4i%1.
.BEGIN TABIT1(20);GROUP;
That is:
%d(l#:#<x,v>)%1 is: %9λ%d(v%41%*)%2\if %dv = %aU%* %2then %aU%2
\else if %dv%41%* = %aU%2 then %aU%2
\else if %dv%41%* = x%2 then %dv%2
\else %dl(v%41%*)%1.
where: %2if%d p%* then %dq%* else %dr%1 is %dcond(p,q,r)%1.
.END
Now let's begin to clarify the mathematical content of the operator, "<=".
The device we use in LISP to name functions is %3label%*. Though {yonss(P90)} makes it
clear that a simple-minded approach is doomed, let's see how far it %2will%* go.
As before, we take our clues from the behavior of %3eval%* and %3apply%*.
In any environment %9D%4a%1 should map %3label[f;g]%* in such a way that the
denotation of %3f%* is synonymous with that of %3g%*.
That is, %df%* is a mapping satisfying the equation
%df(t%4i%*,#...,#t%4n%*)#=#%dg(t%4i%*,#...,#t%4n%*)%1.
So:
.END
.BEGIN TURN OFF "{","}";CENTERIT;FILL;TURN ON "#";
←%9D%4a%1{%3label[%af%1;%ag%*]}%d(l)%1#=#%9D%4a%1{%ag%1}%d(l)%1.
.END
This will suffice for our current λ-definitions; we need not modify %dl%*
since the name %3f%* will never be used within the evaluation of
an expression involving %3g%*.
.BEGIN TURN ON "#";
By now you should be getting suspicious that all is not quite right. We will
now justify your discomfort. First, our proposed description of the meaning
of λ-notation is a bit too cavalier. Our treatment of evaluation of free
variables in LISP (on {yon(P93)} and in {yonss(P77)}) shows that free
variables in a function are to be evaluated when the function is %2activated%*
and %2not%* when the function is defined. Thus a λ-definition generally
requires an environment in which to evaluate its free variables.
So its denotation
should be a mapping like: %denv%*#→#[%aS%9*%1#→#%aS%*] rather than
simply %aS%9*%1#→#%aS%1. Is this consistent with our understanding of the
meaning of λ-notation? Yes.
It is exactly what %2⊗→closure↔←%* was attempting to
describe. What we previously have called an ⊗→open function↔← is a creature of the
form:
%aS%9*%1#→#%aS%*.
.END
This enlightened view of λ-notation must change our conception on %denv%* as well.
Now, given a name for a function in an environment we can expect to receive
a mapping from %denv%* to an element of %aFn%*. I.e. for such names:
.BEGIN CENTERIT;
←%denv %1is the set of functions: %aId%1 → [%denv%1 → %aFn%1]
.END
We will let you ponder the significance of this statement for a few moments
while we continue the discussion of "<=".
A modification of our handling of %3label%* seems to describe the case
for recursion:
.BEGIN TURN OFF "{","}";CENTERIT;FILL;TURN ON "#";
←%9D%4a%1{%3label[%af%1;%ag%*]}%d(l)%1#=#%9D%4a%1{%ag%1}%d(l#:#<f,%9D%4a%1{%ag%1}%d>)%1.
.END
Interpreting this equation operationally, it says: when we apply a %3label%*
expression in an environment it is the same as applying the body of the definition
in an environment modified to associate the name with its definition.
This is analogous to what the LISP %3apply%* function will do.
Recalling the inadequacy of this interpretation of %3label%* in more
general contexts ({yon(P94)}),
we should perhaps look further for a general reading of %3label%*. Our hint
comes from our interpretation of "<=" as an equality. I.e., recall:
.BEGIN CENTER;SELECT 3;TURN OFF "←";
fact ← %1a solution to the equation:%* f = λ[[x][x=0 → 1; T → *[x;f[x-1]]]].
.END
What we need is a representation of an "equation-solver" which will
take such an equation as input and will return as value a function
which satisfies that equation. In particular we would like the %2best%*
solution in the sense that it requires the minimal structure on the function.
⊗↓Like a free group satisfies the group axioms, but imposes no other
requirements.←
This request for minimality translates to finding the function which
satisfies the equation, but is least-defined on other elements of the
domain. Though a full discussion of "least" brings in the recent work of D. Scott
and is a bit too advanced for our purposes, the intuition behind
this study is quite accessible and again illuminates the distinction
between mathematical meaning (denotational) and manipulative meaning (operational).
Consider the following LISP definition:
.BEGIN CENTER;SELECT 3;
f <= λ[[n][n=0 → 0; T → f[n-1] + 2*n -1]]
.END
.BEGIN TURN ON "#";
When we are asked what this function is doing, most of us would proceed
operationally; that is, we would begin computing %3f[n]%* for different
values of %3n%* --what#is#%3f[0]?%*,
what is %3f[1]%1,#...#. It is profitable to look at this process differently:
what we are doing is looking at a %2sequence%* of functions,
call them %df%4i%1's .
.END
.BEGIN TABIT3(10,16,44);SELECT d;GROUP;TURN OFF "{","}";
\f%40%1 =\%d{<0,%aU%*>,<1,%aU%*>, ... }\%1when we begin, we know nothing.
\%df%41%1 =\%d{<0,0>,<1,%aU%*>, ... }\%1now we know one pair.
\%df%42%1 =\%d{<0,0>,<1,1>, ... }\%1now two
\%df%43%1 =\%d{<0,0>,<1,1>,<2,4>, ... }\%1now three
\ ...\ ... ...\%dEureka!!
.END
When (if) the sudden realization strikes us that the LISP function is
"really" (denotationally) %dn%82%1 on the non-negative integers,
then we may either take
that insight on faith or subject it to proof. The process of discovering
the denotation can be construed as a limiting process which creates
the least-defined function satisfying the LISP definition. That is:
.BEGIN CENTER;SELECT d;
%9λ%d((n)n%82%d)%1 = %1least upper bound of%d f%4i%1's;
.END
where %df%4i%1 may also be characterised as:
.BEGIN TABIT1(12);SELECT D;group;
\ %1|%d n%82%1 if %d0%c≤%dn%c≤%di
f%4i%d(n)%1 =\<
\ | %aU%1 if %di%c<%dn
.END
We may think of our "equation-solver" as proceding in such a manner.
Though it is not at all obvious, such an equation solver
%2does%* exist; it is called the %2⊗→fixed-point operator↔←%* and is
designated here by %dY%*. We will now give an intuitive derivation of %dY%*.
In terms of our example we want a solution to %df = %9t%d(f)%1, where:
.BEGIN CENTER;
%9t%d(g) = %9λ%d((n) cond(n=0, 0, g(n-1)+2*n-1))%1,
.END
Our previous discussion leads us to believe that
%9λ%d((n)n%82%d) %1for %dn %c≥%d0%1 is the desired solution.
.BEGIN TURN ON "#";
How does this discussion relate to the sequence of functions %df%4i%1?
First, it's important to keep the domains of our various mapping in mind:
%df%*#%9ε%*#Fn and %9t%* is a functional in %aFn%1#→#%aFn%1.
Let's look at the behavior of %9t%* for various
arguments. The simplest function is the totally undefined function, %aU%*#⊗↓We
perhaps should subscript %aU%* to distinguish it from previous %aU%*'s.←.
.BEGIN CENTER;
%9t%d(%aU%*) = %9λ%d((n) cond(n=0, 0, %aU%*(n-1)+2*n-1))%1,
.END
but this says %9t%d(%aU%*)%1 is just %df%41%1!
Similarly,
.BEGIN CENTER;
%9t%d(%9t%d(%aU%*))#=#%9λ%d((n) cond(n=0, 0, f%41%*(n-1)+2*n-1))%1,
.END
is just %df%42%1.
Thus, writing %9t%8n%1 for the composition of %9t%1...%9t%1, n times, ⊗↓Define
%9t%80%1 to be the the totally undefined function, %aU%1.← we can say
.BEGIN CENTER;GROUP;
%df%4n%* = %9t%8n%d(%aU%*)%1 or,
%9λ%d((n)n%82%*)%1 = lim%4n=0 → ∞%9t%8n%d(%aU%d)%1.
.END
Or in general the fixed-point of an equation %df = %9t%*(f)%1 satisfies the
relation:
.BEGIN CENTER;
%dY(%9t%*) = lim%4n→∞%9t%8n%d(%aU%d).%1
.END
Thus in summary, %dY%* is a mapping:[%aFn%* → %aFn%*] → %aFn%*
such that if %9t%*#%9ε%*#[%aFn%*#→#%aFn%*] and %df%*#=#%9t%d(f)%1, then
%9t%d(Y(%9t%*))%1#=#%dY(%9t%*)%1 and %dY(%9t%*)%1 is least-defined of any of the solutions
to %df%*#=#%9t%d(f)%1.
.END
So the search for denotations for %3label%* might be better served by:
.BEGIN TURN OFF "{","}";CENTERIT;FILL;TURN ON "#";
←%9D%4a%1{%3label[%af%1;%ag%*]}%d(l)%1#=
#%dY(%9λ%d(h)%9D%4a%1{%ag%*}%d(l%1#:#%d<f,h>))%1.
.END
Which characterization of %3label[f;g]%* is "better"?
The first denotation parallels the behavior of %3eval%* and %3apply%*, applying
%3g%* in a %denv%* modified by the pair %d<f,g>%*.
The later fix-point characterization says %3label[f;g]%* is a particular
solution the the equation %3f=g%*. As we have seen, the "meaning" of %3label%*
is better served by this fix-point interpretation. The crucial questions, however,
are: first, are these two denotations different?
And which, if either, interpretation is %2correct%*?
That is, which
characterization has the same %2effect%* as %3eval%* and %3apply%*?
.BEGIN TURN OFF "{","}";TURN ON "#";
First, the characterizations are %2not%* the same. Examination of the
behavior of %9D%4e%1{%3label[car;car][(A#B)]%1} will exhibit a discrepancy.
.END
The general question of the correctness of the denotational semantics which we
are developing is the subject of much of M. Gordon's thesis.
***add lisp induction***
The intuitions presented in this section can be made very precise.
The natural ordering
of "less defined" exemplified by the sequence of %df%4i%1's: %df%4i%1 is less
defined (or approximates) %df%4j%1, j%c≥%1i, imposes a structure on our domain of functions.
Indeed, a structure can be naturally superimposed on all of our domains.
If we require that some additional simple properties hold on our domains, then
the intuitions of this section can be justified mathematically.
*** ADD MONOTONICITY, CONTINUITY
The papers of Scott, Gordon, and Wadsworth supply the missing precision.
In case you think least fixed points are too removed from the realities of
programming language design, please refer to {yon(P94)} again.
Though intuition finally uncovered a counterexample to the general application
of the specific implementation of LISP's %3label%*, intuition has been guilty
of superficiality here. The nature of recursion is a difficult question and
this fixpoint approach should make us aware of the pitfalls.
Actually we glossed over a different kind of fixed point a few moments
ago:
.BEGIN CENTERIT;
←%denv%1 is the set of functions %aId%1 → [%denv%1 → %aFn%1]
.END
This statement requires a fixed point interpretation to be meaningful.
Finally stirring denotations for simple variables back into our %denv%*,
we are led to an adequate description of environments for LISP:
.BEGIN CENTERIT;
←%denv%1 is the set of functions %aId%1 → [%denv%1 → %aFn%1∪%aS%1]
.END
**structure of domains**
**justification**
Recalling that this characterization of %denv%* arose in explicating
free variables, it should not come as too much of a suprise that
we must modify the fix-point characterization of %3label[f;g]%*.
We had assumed that %3f%* and %3g%* were in %aFn%*, whereas they are
in %denv%*→%aFn%1. %3label[f;g]%* binds %3f%* to %3g%* in an environment,
leaving free variables in %3g%* unassigned. These free variables of %3g%*
are evaluated in the environment current when the %3label%*-expression
is applied. Thus the meaning of a %3label%*-expression should also be a
member of %denv%*→%aFn%1. So:
.BEGIN TURN OFF "{","}";CENTERIT;FILL;TURN ON "#";
←%9D%4a%1{%3label[%af%1;%ag%*]}%d(l)%1#=
#%dY(%9λ%d(h)(%9λ%d(l%9*%d)(%9D%4a%1{%ag%*}%d(l%9*%1#:#%d<f,h>)) ))(l)%1.
.END
Notice that all our work on fixed-points and recursion equations has only
involved %2single%* equations. Indeed, the label operator can only define
a single function. Frequently a function needs to be defined via a %2set%*
of recursion equations. In particular when we wrote %3eval%* and %3apply%*
we were really asking for the solution to such a set of equations: %2⊗→mutual recursion↔← equations%*.
When we wrote:
.BEGIN TABIT1(30);SELECT 3;GROUP;
\eval <= λ[[e;a] ...
\apply <= λ[[fn;x;a] ...
.END
As we said in {yonss(P38)}, we really meant:
.BEGIN TABIT1(30);SELECT 3;GROUP;
\label[eval; λ[[e;a] ... ]
\label[apply; λ[[fn;x;a] ...]
%1 where %3eval%* and %3apply%* occur within the %3λ%*-expressions.
.END
That is:
.BEGIN TABIT1(30);SELECT 3;GROUP;
\label[eval; %9F%1(%3eval,apply%1)]
\%3label[apply; %9Q%1(%3eval,apply%1)]
.END
Now since LISP doesn't allow %3label%* to express mutual recursion directly,
we must resort to a subterfuge if we wish to express such constructions in LISP.
Namely:
.BEGIN CENTER;SELECT 3;
label[eval; %9F%1(%3eval,label[apply; %9Q%1(%3eval,apply%1)]%1)]
.END
Clearly this subterfuge is applicable to the definition of other
(mutually recursive) functions; but subterfuge, it is. To really be
useful, we realize that LISP must at least allow a %2sequence%* of
definitions to be given such that these definitions will be in effect
through some reasonable calculation.
There is minimal insight gained by thinking
of our LISP functions as anonymous solutions to a gigantic fixpoint equation.
Sequencing, thus is important. Sequencing is implicit in the order
of evaluation of arguments expressed in %3eval%*; sequencing is
implicit in the evaluation of ⊗→special form↔←s.
Certainly sequencing has become quite explicit by the time we examine %3prog%*.
All of these manifestations of sequencing have been abstracted out in the
denotational approach.
It is natural to ask whether there is some way to introduce
sequencing into our formalism so that more realistic implementations
can be proved correct.
***continuations: extensions to sequencing and order of evaluation***
After all this work there really should be a comparable return on
on our investment. We believe there is. An immediate benefit is
clearer understanding of the differences between mathematics and programming
languages.
A clearer perception of the role of definition and computation.
Later we will see that the thought required to specify domains and
ranges of functions is directly applicable to
the design of an extension to LISP which allows user-defined
data structures.
.CENT(Problems);
%2I%* What is the %2statement%* of the correctness of %3eval%* in terms
of the denotational semantics?
.SEC(Running on the machine)
%1
This section is for the brave few who wish to run on a machine.
The %2programming language%*, LISP, is the Sexpr translation
of the LISP functions and %3prog%*s that we have been writing. What are
some of the implications of writing in Sexpr form?
First, LISP becomes the world's largest parenthesis sink. It makes
for difficult reading at times, but there are formatting tricks, and
editing programs which will help the user match parens and locate
parts of the program. (It only hurts for a little while). There is
a practical benefit which greatly outweighs this anguish factor:
since proper input to LISP programs are Sexprs and since we are writing
LISP programs in Sexpr form then on input, data and program are
indistinguishable in format; i.e., the are both binary trees.
Obviously for evaluation, programs must have a very special structure,
but program and data are both trees just as in more hardware machines
the contents of locations which contain data are indistinguishable
in format from locations which contain instructions.
On the bare machine it is the way in which a location is accessed
which determines how the contents of that location are interpreted.
If the central processor accesses the location via the program
counter, the contents are assumed to be an instruction. That same
location can usually be accessed as part of a data manipulating
instruction. In that case, the contents are simply taken to be data.
LISP is one of the few high-level languages which also has this property.
It gives the programmer exceptional power. Let's complete the
analogy. The central processor here is our old friend, ⊗→%3eval%*↔←.
If %3eval%* references a binary tree via its `program counter', then
that tree is decoded via the internals of %3eval%*. If a tree is
referenced as input to an Sexpr-massaging function, then it is
taken as data. As a result, a LISP program can %3cons%*-up a new
Sexpr which can then be evaluated (i.e., interpreted as an intruction).
The simplest way to communicate with such a machine is to read an
sexpr translate of a LISP expression into memory, evaluate the expression, and
print the result. Several implementations of LISP use a slight variant
of this called the "read-eval-print" loop:
←%3prog[[]##a##print[eval[read[];NIL]];go[a]]%*.
.BEGIN TURN ON "#";
Since programming is done using the sexpr translation of LISP functions
it becomes convenient to sometimes say "...#the function %3CAR%*#..." or
"...#write a %3PROG%*#...",#... when we actually mean %3car%* and %3prog%*,#....
The actual LISP functions are written in the language generated by syntax equations
which we have been including. This language is called the meta-language, and
the LISP expressions called ⊗→M-expressions↔← or M-exprs.
The distinction between Mexprs and their Sexpr translations must not be forgotten.
.END
Though %3eval%* is the equivalent of the basic Cpu of the ⊗→LISP machine↔←,
there is another artifact in many versions of LISP to communicate
with the outside world. As with most pieces of I/O equipment,
it leaves something to be desired. Its name is %3evalquote%*.
.SS(%3evalquote%*,%3evalquote%*)
The basic structure of the %3evalquote%*-loop is:
%21.%* read in a (Sexpr representation of) function . I.e., a name
or a lambda expression.
%22.%* read in a list of (evaluated) arguments to be applied to the function.
%23.%* apply the function (of step %21.%*) to the argument list.
%24.%* print the value.
%25.%* go to step %21.%*
Thus the structure of the loop is essentially:
.BEGIN TABIT2(24,27);TURN OFF "←";
%3
.GROUP
prog[[fn;x;z]
\l\fn ← read[ ];
\\x ← read[ ];
\\z ← evalquote[fn;x];
\\print[z];
\\go[l]]]
%1where: %3evalquote <= λ[[fn;x]apply[fn;x;NIL]]
.APART
%*
or more concisely:
%3
.GROUP
\prog[[ ]
\ l print[evalquote[read[ ];read[ ]]];
\ go[l]]
.APART
%*
.END
.GROUP
where:
%21.%* the function, ⊗→%3read%*↔←, negotiates with an input device to read an
Sexpression.
%22.%* the function, ⊗→%3print%*↔←, prints the value of its argument on an output
device.
.APART
The details of %3read%* and %3print%* will appear when we discuss implementation
of LISP.
.BEGIN TURN ON "#";
Here's an example of the behavior of %3evalquote%*. Assume that the input
device contains %2CAR#((A#B))%*. Then the first %3read%* in %3evalquote%* gets
%2CAR%* (a string representing an Sexpr), and the second read gets %2((A#B))%*;
then %3apply%* gets called as:
%3
←apply[CAR;((A B));NIL].
%*
%3apply%* says that this is the same as evaluating
%3car[(A#B)]%*, and thus returns %3A%* as its answer, which is dutifully
printed by %3print%*.
.END
So %3evalquote%* can be used as a `desk calculator' for LISP.
If we wish to evaluate an expression %3f[a%41%*;#...#a%4n%*]%1 for
%3a%4i%1 constants, i.e. sexprs, then %3evalquote[F;#(a%41%*#...#a%4n%*)]%1
will do it for us. But the %3evalquote%*-loop will %2not%* evaluate arguments;
the a%4i%1's in the call on %3evalquote%* are not expressions, not translates
of constants, but are constants.
Typing %2CONS#((CAR#(QUOTE#(A)))#(QUOTE#(B)))%* to the %3evalquote%*-loop
will result in %3((CAR#(QUOTE#(A)))#.#(QUOTE#(B)))%*.
The %3evalquote%*-loop is an anomaly. It does not expect the usual representation
of a LISP form say %3(F e%41%* ... e%4n%*)%1 where the %3e%4i%1's
are to be evaluated. It expects a %2pair%* of sexprs representing a function
and %2evaluated%* arguments. The benefits of having "functional-notation" as
input and having arguments implicitly evaluated are greatly outweighed
by the confusion introduced by having two formats for LISP expressions, one for
the "top-level" and a different one everywhere else.
Certainly
before we can do any reasonable amount of calculation, we must be
able to define and name our own functions. The %3label%* operator, or
calling %3eval%* with an intial symbol table containing
our definitions will suffice, but this is not particularly elegant.
We would like our definitions to have some permanence.
A function (actually a %2special form%*, if you have been paying attention)
named ⊗→%3define%*↔←, whose effect is to add definitions to %3apply%*, has been
provided. The actual behavior of %3define%* will appear in the sections on
implementation.
.P51:
%3define%* is the name of a special form (its arguments are not evaluated)
of one argument, say %3x. x %*is a list of pairs: %3((u%41%* v%41%*) ... (u%4n%* v%4n%*)).%1
Each %3u%4i%1 is the name of a function and each %3v%4i%1 is the λ-expression
definition. Actually each %3u%4i%1 and %3v%4i%1 is the %2Sexpr translation%* of the
name and the function, but you knew that anyway. The effect of %3define%*
is to put the appropriate definitions in the symbol table.
For example we might wish to define the function which reverses a list as:
%3
.BEGIN NOFILL;TURN OFF "←";
.GROUP
reverse <= λ[[x] prog[[y;z]
y ← x;
z ← NIL;
a [null[y] → return [z]];
z ← cons[car[y];z];
y ← cdr[y];
go[a];]]
%1
.APART
Then the following would make this definition grist for the %3evalquote%* mill.
.GROUP
%3
DEFINE((
(REVERSE (LAMBDA (X)
(PROG (Y Z)
(SETQ Y X)
(SETQ Z NIL)
A(COND ((NULL Y)(RETURN Z)))
(SETQ Z (CONS (CAR Y) Z))
(SETQ Y (CDR Y))
(GO A) )))
))
%1
.APART
and subsequently:
%3REVERSE ((A B C)) %1would evaluate to: %3(C B A).%1
.END
%1
C. Weissman's LISP PRIMER is an excellent source of machine examples
and should be consulted now. Always remember that you are writing the sexpr representation
of LISP functions and expressions. Do not confuse the two.
.SS(A project: extensions to %3eval%*,%3eval%*,P67:)
.SELECT 1;
***h.s. about how wonderful LISP is for extenson***
.BEGIN TURN ON "#";
Consider a p%4i%* → e%4i%* component of a conditional expression. As
conditionals are now defined, e%4i%* must be a single expression to be evaluated.
In subsets of LISP without side-effects this is sufficient. It is, however,
convenient in practice, i.e., in LISP %2with%* side effects, to extend conditionals to include components of the
form: p%4i%*#→#e%4i1%*; ... e%4in%*.
This extended component is to be evaluated as follows: if p%4i%* is true, then
evaluate the e%4ij%*'s from left to right, with the value of the component to be
the value of e%4in%*.
For example, this feature, used in %3prog%*s would allow us to replace:
.BEGIN TABIT2(10,14);
\\ ....
\\[p%41%* → %3go[l]%1]
\\ ...
\%3l\%1e%41%*;
\\e%42%*;
\\ ...
\\%3go[m];
.END
with: [p%41%* → e%41%*;e%42%*; ... %3go[m]%*;]. This is certainly easier to read.
This extended conditional expression is available on versions of LISP 1.6 on the PDP-10.
Here is another cosmetic. Instead of requiring that the body of a λ-definition
be a single expression: %3λ[[#...#]f[#...#]]%*, allow bodies of the form:
%3λ[[#...#]f%41%*[#...#];#...#f%4n%*[#...#]]%1. The evaluation of such
should mean; bind as usual, evaluate the %3f%4i%1's from left to right, returning
as value %3f%4n%*[#...#]%1.
This next extension to %3eval%* was derived from the syntax of ⊗→MUDDLE↔←, ⊗→CONNIVER↔←, and
⊗→MICRO-PLANNER↔←.
We have seen that LISP calling sequences are of two varieties: functions calls,
evaluating %2all%* of the arguments; and special forms, evaluating %2none%* of the
arguments.
In an attempt to generalize this regime we might allow the evaluation of some
of the arguments and enlarge on the domain
of objects which can appear in the list of λ-variables.
We might partition the formal parameters into obligatory parameters, optional
parameters, and an excess collector.
Obligatory parameters %2must%* have corresponding actual parameters; optional
actual parameters are used if present, otherwise declared default
values are used; and
if there are more actual parameters than the formals encompassed by the first
two classes, then they are associated with the excess collector.
To be more precise consider the following possible BNF equations:
.BEGIN TABIT1(13);TURN OFF "←";
<varlist>\::=[<obligatory> <optional> <excess>]
<obligatory>\::= <par>; ...<par> | %cε%*
<optional>\::= "optional" <opn>; ... <opn> | %cε%*
<excess>\::= "excess" <par> | %cε%*
<par>\::= <variable> | @<variable>
<opn>\::= <par> | <par> ← <form>
.END
The associated semantics follows:
.BEGIN INDENT 0,10;TURN OFF "←";
%21.%* The formal parameters are to be bound to the actual parameters from
left to right (as usual).
%22.%* There must be an actual parameter for each obligatory parameter, and
if there is no excess collector there may not be more actual parameters than
formals. (There may be less if we have optionals.)
%23.%* If a <variable> in a formal parameter is preceeded by a "@", then
the corresponding actual parameter is %2not%* evaluated.
%24.%* We might run out of actual parameters while binding the optionals.
If we do, then we look at the remaining formal optionals.
If a formal is simply a <par> then bind it to %3NIL%*; if a formal is
@<variable> ← <form> then bind the <variable> to the <form>; or if the formal is
<variable> ← <form>, bind <variable> to the value of <form>.
%25.%* Finally, the excess collector is bound to a list of any remaining
actual parameters in the obvious way: if <par> is <variable> then form a list
of the values of the remainder; if it is @<variable>, bind <variable> to the
actual list. If there is no excess, bind to %3NIL%*.
.END
.BEGIN TURN OFF "←";
These same languages have extended %3prog%*-variables slightly, allowing
them to be initialized explicitly. If a %3prog%*-variable is atomic,
intialize it to %3NIL%*, as usual. If it is of the form <variable>#←#<form>
then initialize it to the value of the <form>.
.END
.END
.BEGIN TURN OFF "←";turn on "\"; tabs 10,20;
Here are some examples:
1. In the initialization of %3length%* on {yon(P45)}, we could write:
%3...#prog[[l#←#x;#c#←#0]#....%*
2. %3list%* could now be defined as: %3λ[[%1"excess"%* x]x]%*.
3. Consider the following definition:
.BEGIN NOFILL;
.group
\%3baz <= λ[\[x;%1@%*y;%1"optional"%* z; u ← 0; %1"excess"%* v]
\\print[x];
\\print[y];
\\print[z];
\\print[u];
\\print[v]].
.APART
%1Then a call of:
%3eval[(BAZ 2 (CAR (QUOTE (X Y)) 4 5 6 7 (CAR (QUOTE (A . B))));NIL]%* would print:
%3
2
(CAR(QUOTE (X Y))
4
5
(6 7 A)%*
(and return value: %3(6 7 A)%*.
Similarly defining;
.GROUP
\%3fii <= λ[\[x;y;%1"optional"%* z; u ← 0; %1"excess"%3 v]
\\print[x];
\\print[y];
\\print[z];
\\print[u];
\\print[v]].
%1and calling:
%3eval[(FII 2 (CAR (QUOTE (X Y)));NIL]%* prints:
%3
2
X
NIL
0
NIL.%*
.END
.END
←%2Problems%*
Design simple sexpr representations of these proposed constructs.
Make these extensions to %3eval%*. How useful are these syntactic
sugarings?
.SS(A project: Syntax-directed processes,syntax-directed)
%1
.REQUIRE "NOTES.SDP" SOURCE_FILE;
.SEC(Implementation of the Static structure of LISP,static structure)
.TURN ON "←","α";
%1
.SS(Introduction,symbol tables)
The material in the previous chapters has been rather abstract and
perhaps the more practical-minded reader is becoming skeptical of
this whole endeavor ⊗↓"Oh, ye of little faith!"←.
This chapter begins a discussion of the actual mechanisms which
underlie a typical implementation of LISP. However the importance of the
techniques we will describe extends far beyond the implementation of
this particular language. Most of the ideas involved in our implementation
are now considered standard system programming techniques and
are common tools in language design. LISP is particularly well-suitede
to the task of explicating these ideas since many find their origins in
the first LISP implementation.
We will begin our discussion of implementation with an analysis of
storage regimes for S-expressions. As with the more abstract discussions
of representations,
the "concrete" representation which we pick for our data structures (s-expressions)
will have direct bearing on the implementation of the primitive constructor
(%3cons%*), selectors (%3car, cdr%*) and predicates (%3atom, eq%*) of LISP.
Since we are now attempting to become less mathematical and more practical,
we must worry about the efficiency of the implementation
⊗↓But not to the detriment of generality or good program design.←, and we must
worry about input/output mechanisms so that the language may communicate with the
external world.
The present chapter will develop a picture
of this %2static%* structure of an implementation, or perhaps to be more
graphic, this chapter discribes the memory of a LISP machine.
The next chapter discusses the control structures necessary to properly
evaluate expressions involving recursive functions. The description
of the %2dynamic%* structure of LISP is a natural setting in which to
discuss compilers for LISP. For example a complier, when given a form,
generates machine instructions, which when
executed will have the same computational effect as the evaluation of
the form by the interpreter. The code generated by the compiler must obey
all of the control structure conventions imposed by the implementation.
As we handle the questions of compilers, we will discuss the dynamics
of LISP.
Throughout these discussions we will
walk a narrow line, attempting to remain as abstract as
possible without losing too much detail, while at the same time, not
degenerating into a discussion of coding tricks. Thus we will attempt
to describe the "logical" structure of a LISP machine, even though
an efficient implementation might map differing logical structures onto
the same physical structures by utilizing machine-dependent techniques.
As a gesture of good faith we will now resurrect our "box-notation" for S-expressions
({yon(P102)})
and show how this notation mirrors the logical
(and usually physical) structure of LISP memory, and show how to represent
simple LISP operations in a concise graphical notation which manipulates these boxes.
Actual hardware instructions usually exist to simulate these manipulations.
.SS(AMBIT/G,AMBIT/G,P26:)
.SELECT 1;
AMBIT/G⊗↓An ambit is half aminal, half hobbit. AMBIT/G also is an acronym
for Algebraic Manipulation By Identity Transformation/Graphical.←
is a graphical language for the description of both
data and algorithms. We will explore a few aspects of AMBIT,
using it only to describe most of the basic operation of LISP. AMBIT
is a powerful graphical language suitable for describing complicated
data structures and their manipulation. A crucial problem of non-numerical
applications is the structuring of the data. Indeed it is frequently the case
that the structuring of the data is the %2only%* problem; once the
proper representation has been established a very simple program to
manipulate the complex representation will suffice. Often
what appears to be a complicated algorithm is, in reality, a simple algorithm
operating on complex data.
A poor representation will lead to an inefficient program.
Therefore in AMBIT, programming is attempted only after the data design
has been completed.
Since the
interrelationships between data structures are inherently more static than
the executing of an algorithm, it is also beneficial to separate complex data
from simple program ⊗↓Perlis: "suppress the constant and display the variable".←.
Proofs of correctness of programs designed in this way should also be more easily
obtained. There are difficulties in designing programs in this manner; a
significant difficulty lies in the paucity of notation which we have available
for describing algorithms. Current notations for programming languages are derived
from linear mathematical notations. These notations are ill-suited for
describing data structure representations.
As a very simple case, functions in mathematics are single-valued, but often
in programming we would like to return more than one value. In particular we
would like to return values which can be used immediately as arguments to another
function. A generalized composition if you wish. Mathematical notation
is not conducive to such operations even though the operations is
quite natural and easily understood from the model of execution.
If we do not want to use a high level language then
the other common choice is to encode the
algorithm in machine language. The objections to this approach are clear: the
program is incomprehensible to other people, and all too frequently it is
poorly understood even by its creator.
When we think about writing a complex non-numerical program like a compiler,
a proof-checker, or a piece of a large system, we frequently draw pictures to
help crystalize our ideas and to structure the data efficiently.
When faced with explaining a complex structure-manipulating
program to someone we draw a picture. Clearly then, a graphical notation
for programming is worth exploring. AMBIT is such a language.
First, the data representation in AMBIT is a generalization of the
%2box notation%* of LISP. We have already seen that it is often
helpful to draw pictures to understand the data representation
in a particular problem. Instead of requiring that we draw all
nodes in a tree as boxes, we might convey more of our intuition
by drawing nodes of different shapes to represent nodes which contain
different kinds of information. We might decide to frame the terminal
nodes in a box:###%7[~~~~~~]%*### just as we draw nonterminal nodes as:
###%7[~~~~]~~~~]%*### even though as far as most machines are
concerned both kinds of nodes map into the same kind of memory cell.
AMBIT/G exploits this generalization of shapes.
This is interesting and useful notation but in
itself gives us no new power. The innovation is that we can
also describe our algorithms as graphical transformations of the
data graphs.
The three components of an AMBIT/G program are declaration,
initialization, and algorithms.
First, we declare the shapes which will be used in
the algorithm and declare the number and relative positions of the
arrows which can radiate from each type of node. The initialization
sets the initial links of the data graph.
The basic statements of the language are %2pattern-match-and-replacement%*
rules. If a designated pattern can be
found in the current state of the data graph, then replace it with
a new pattern. The only kind of replacement allowed is the %2swinging%*
of an arrow so that its head moves from one node to another.
Where the arrow head strikes a node is immaterial; the origin of the tail
%2is%* important.
The tails of the arrows are fixed (as are the number of data nodes
and arrows). The individual statements are combined into an
algorithm by success and failure conditions.
For example, here's %3car%*:
.BEGIN GROUP;SELECT 2;centerit;
.GROUP SKIP 6;
←picture of AMBIT/G algorithm for %3car%*
.END
Now for the explanation.
The general execution of an AMBIT/G block can be described in the usual
paradigm: selection, testing, and construction.
First the data is selected. A match of the nodes and solid links is attempted.
If this match cannot be made, an error has occurred.
The circle is a notational convenience: it matches any shape.
Arrows which are suppressed are not needed for matching.
Next, the testing of circled components is done. If a test fails, then
the failure exit, F, is taken.
Finally the constructions, designated by the dotted links, are performed.
These dotted links then become soild, and the success exit, S, is taken.
Thus in this example, %3car%* would succeed as long as AC1 points to a
non-terminal node; otherwise we get an error.
When it is profitable, we will draw pictures in the style of AMBIT/G,
but we will always be quite informal about it. It should be remembered that
AMBIT/G %2is%* a precise complete language ⊗↓For example AMBIT was used to
document all of BASEL.←. Graphically methods, in general, can be used
with great effect in describing all manner of complex data structure
algorithms ⊗↓T. Cheatham's notes on compiler writing used graphical
methods and AMBIT extensively.←.
We now begin our search for a realistic implementation of LISP, with
a closer look at symbol tables.
.SS(Symbol tables: revisited)
There are some rather gross defects in our symbol table mechanism.
First, (disregarding %3define%*) we have had to resort to subterfuge
to put the definitions of our functions in our symbol table.
Using %3label%* ({yonss(P38)}), or calling %3eval%* with an initial
symbol table, only defines the function for %2that%* particular call
on %3eval%*. When we finish the computation, the definition disappears.
From a practical point of view definitions should have some permanence.
An implemented version of LISP should know a
lot more functions than the five primitives. It should have a
reasonable class of arithmetic functions, and some commonly used
Sexpr functions (like %3length, assoc, subst, equal,%* etc.) all predefined.
If we do things right we should be able to use the mechanism for
predefining functions as the tool for adding our own definitions.
Second, the table look-up mechanism of %3assoc%*, though theoretically
sound, leaves something to be desired as far as efficiency is
concerned. Since we do wish to implement LISP, we should be concerned with
efficient operations. We will see that an efficient and powerful symbol table structure
can be described quite easily in LISP.
Third, we have already seen that special forms %3QUOTE%* and %3COND%* are
not evaluated in call-by-value style.
Currently the recognizers for special forms are encoded in %3eval%*, and
when an instance of such a form is seen the argument is passed %2unevaluated%*
to a function to perform the required operations.
It would be nice to extend this flexibility
to the user. We would like to have notation for adding λ-definitions of
special forms to our symbol table.
%3eval%* would then need a way of distinguishing a
λ-expression defining a function from a λ-expression defining a special form.
Also there are other calling sequences which are interesting and useful and
would be nice to have.
The current version of %3eval%* only handles function definitions. Thus
the current symbol need only store the λ-definition and does not
need explicit information saying it is a %2function%* definition.
Fourth, conceptually we could use a more powerful mechanism. Consider
%3car[car]%* as an expression to be evaluated. Perhaps it is best just
to say the expression is ill-formed, but if you knew that %3car%* also
was currently being used as a simple variable besides being a function,
then your intuition says the first occurrence of %3car%* is a function
name and the second occurrence is the simple variable name; and if the
current value of %3car%* was say, %3(A B)%* then %3car[car]%* should evaluate to %3A%*.
That is, context tells us which occurrence of %3car%* is a function
and which is a simple variable ⊗↓just as an evaluator for %3prog%* can
tell a reference to the label %3x%* from the %3prog%*-variable %3x%* in
%3#...#prog[[x;y]#..#x#f[..]#...#g[x#..#]#...#go[x].%* See {yon(P83)}.←.
The current %3eval%* %2will%* operate correctly on this example since
a recognizer for the function %3car%* is explicitly encoded in %3apply%*.
⊗↓For the same reason, the LISP obscenity %3λ[[lambda] ... ]%* will work.
Notice its sexpr representation is %3(LAMBDA#(LAMBDA)# ...#)%*←.
However, in general our current symbol table mechanism is not sufficient for
this interpretation. Forced to use %3assoc%*,
we would only find the %2first%* binding of a variable. It will either
be a λ-expression (function) or a simple value. Context will determine
how %3eval%* will interpret what is found.
Clearly what is needed is the ability to
associate more than one property with an atom. In the above example
%3car%* has (at least) two %2properties%* or %2attributes%*. It has a function
value and it has a simple value. Since %3car%* is a primitive function,
its function value is the location of the machine code to carry out
the %3car%* function; the simple value is the sexpr currently bound to
the variable, %3car%*.
.TURN OFF "α";
These last three desires, for permanence, generality, and for multiple properties,
can be handled by the same mechanism. Clearly we could continue using an
%3assoc%*-like table, though more complicated, storing information
about what kind of value each dotted pair is. However our desire for
efficiency would certainly not be satisfied. Rather, we will
design a new symbol table which can store with each atom sequences of values and
their types. This gives us multiple properties.
We will make the table %2global%*
to %3eval%* and %3apply%*; these functions will now implicitly refer to that table
and thus need not have an explicit symbol-table argument. This
gives us permanence.
We will designate an indicator for function definition and an indicator
for special form definition and expand %3eval%* and %3apply%* to recognize
these indicators. This gives us generality.
Most implementations of LISP allow this association of
arbitrary sequences of %6attribute-value%* pairs with an atom.
It is a very good idea.
How can we associate an arbitrary collection of objects with
something? With each atom we will
associate a list called the %6⊗→property-list↔←%* or p%6-list.%* But atoms
can't be represented as just any other list. Among other things,
we must be able to recognize the occurrence of atoms so that we can
implement the predicate, %3atom%*. So atoms are special lists: the
%3car%* (or first element) of the representation of each atom is an
indicator used exclusively for the beginning of atoms.
We will use %7α%* to designate the beginning of an atom.
The %3cdr%* of the representation of the atom is the property list.
The elements of the p-list are associated in pairs. The first element is
the attribute (or property or indicator); the next element is the value.
For example, here
is part of the atom-structure for %3car%* assuming %3car%* is also being
used as a simple variable and has current value, %3(A B)%*:
.group
.GROUP SKIP 6;
.P50:
←%2Atom-structure for %3CAR%1.
.apart
The indicator, ⊗→%3SUBR%*↔←, tells us that %3car%* is a machine
language function. The indicator, ⊗→%3VALUE%*↔←, tells us that %3car%* is
also being used as a simple variable.
The reason for not pointing directly at %3(A B)%* is described
in {yonss(P5)}.
It should now be clear how
to program the primitive predicate, %3atom%*: "is %3car%* of the argument
to ⊗→%3atom%*↔← the special atom-indicator?" If it is then %3atom%* gives
value %3T%*, otherwise %3atom%* gives value %3NIL%*.
.BEGIN GROUP;SELECT 2;centerit;
.GROUP SKIP 6;
←picture of AMBIT/G algorithm for %3atom%*
.END
.P29:
How about the representation of non-primitive functions?
Non-primitive functions are defined using λ-expressions. What we do is
define a new indicator, ⊗→%3EXPR%*↔←, which tells
the evaluator that the function is a λ-expression. For example,
here is part of the atom-structure for %3FACT%*, the Sexpr form
of the factorial function.
.<<atom struct for fact>>
.GROUP
.GROUP SKIP 15;
←%2Atom-structure for %3FACT%1.
.APART
This picture should tell you at least two things: one, that programs
are (almost) stored as binary trees, and two, it should tell you what the function,
⊗→%3define%*↔←, does. %3define%* ({yon(P51)}) puts the λ-definition under the indicator %3EXPR%*
on each of the named atoms (functions).
The world becomes much simpler if we store each atom uniquely.
This is the reason for saying "almost" above. That
is, every reference to the atom %3A%* is actually a pointer to the same
"binary tree", the binary tree whose %3car%*-part is the special atom indicator,
and whose %3cdr%*-part is the ⊗→p-list↔← for the atom %3A%*. Thus %3(A . A)%*, which
.GROUP
we have been representing as:
.BEGIN NOFILL;TURN ON "\";TABS 30;
\%7[~~~][~~~]
\%3 A A
%1
is more realistically represented as:
\%7[~~~][~~~]
\%1 to atom-structure for %3A%1.
.END
.APART
.P48:
So the internal structures of this implementation of LISP are not binary trees;
there are intersecting branches. Structures of this sort
we will call %2⊗→list structure↔←%*.
LISP thus deals generally with binary list structure.
Trees are a subset of list structures.
We will see in a moment that many of the
computations which we have been performing have also been generating
list structure.
Question: Assume we have the above dotted pair as a value of a variable %3x%*
and we wish to print the value of %3x%*.
Clearly we would hope to see "%3(A . A)%*" appear on the output device.
We would expect that the print routine, named %3print%*, would be given
a pointer to the dotted pair. %3print%* can recognize that it %2is%* a dotted
pair since %3car%* of it is not %7α%*.
But how can %3print%* distinguish %3(A . A)%* from %3(B . B)%* for example.
The pointer in the preceding diagram will point to %3A%* in one case
and to %3B%* in the other but nothing in our representation tells us %2what%*
to print. The simplest thing to do is to store in
each atom-structure some information telling what the name of the atom is.
This is done with another indicator called ⊗→%3PNAME%*↔←, standing for
%2⊗→print-name↔←%*. Thus the atom %3BAZ%* will have at least the following:
.GROUP
.GROUP SKIP 6;
←%2Atom-structure for %3BAZ%1.
.APART
.TURN OFF "#";
The indicator is called %3PNAME%* because the print-name (or ⊗→p-name↔←)
of the atom is what the LISP output routine will print as the name of
the atom. %2BAZ##%* means a memory location
containing some encoding of the letters %2B%*, %2A%*, and %2Z%*.
The symbol, %2#%*, represents some non-printing character; thus we
are assuming a location can contain five characters.
We represent the print-name as a list so that we may allow atoms with
p-names of unbounded length. Thus the p-name for %3BLETCH%*,
would be:
.TURN ON "#";
.GROUP
.GROUP SKIP 6;
←%2P-name structure for %3BLETCH%1.
.APART
How do we get atoms stored uniquely? ⊗→%3read%*↔← does it. On reading
an atom name (which is the way almost all atoms come into existence),
the %3read%* program checks the current symbol table. If the atom does
not appear we add a new entry consisting of the p-list with a single
attribute-value pair ----#the#%3PNAME%*,#p-name#pair#---. If the atom %2does%*
appear, we bring back a pointer to the appropriate entry.
Before talking more about %3read, print%* and the other input-output functions in LISP,
we should discuss the storage of list structure. The implementation
described closely follows that for the PDP-10, though most of
the description is machine independent.
First, though Sexprs and now atoms are represented as binary list structure, there will
be quantities which we wish to represent in memory which are not
structures. For example, numeric constants, and the actual encoding of
print-names for atoms are not structures. These quantities will be stored
in an area called %2⊗→full word space↔← (⊗→FWS↔←)%*. Most of the business of
LISP is massaging of list structure and binary trees, however; such nodes, which have a
%3car%*-part and a %3cdr%*-part are stored in a separate area called
%2⊗→free-space↔← (⊗→FS↔←)%*.
The name, free space, will become apparent in a moment. Each machine
word in FS is divided into two parts; the left half contains a pointer to
the %3car%*-part and the right half contains a pointer to the %3cdr%*-part.
The pointers may point into FS or FWS. In more detail, consider this
representation of
.GROUP
←%3(A .(B . C)):%*
.GROUP SKIP 10;
←%2A representation of %3(A .(B . C))%1.
.APART
Obviously the actual addresses are irrelevant. If we replace the addresses with pointers
to the appropriate cells the resulting diagram will contain the same information.
The origin of the LISP "box notation" should be obvious.
We can now describe an implementation of %3eq%*.
Since atoms are stored uniquely, the predicate, ⊗→%3eq%*↔←,
need only check that its arguments are both atomic and both point
to the same binary tree or location in memory. In most implementations
the check for atom-ness is suppressed and a simple address comparison
is made. Non-atomic sexpessions are not usually stored uniquely. Thus
←%3eq[(A . B);(A . B)]%* is usually false, but
←%3eq[x;x] %*is usually true for any %3x%*.
Please note that we are %2not%* changing the definition of %3eq%*.
%3eq%* is still ⊗→undefined↔← for non-atomic arguments.
The preceding remarks deal only with the usual implementation of %3eq%*.
.BEGIN GROUP;SELECT 2;centerit;
.GROUP SKIP 6;
←picture of AMBIT/G algorithm for %3eq%*
.END
The implementation of %3car%* and %3cdr%* present no problem.
Simple pointer manipulation will suffice.
.P28:
Finally, a remark about conditional expressions. Most versions of LISP
relax the behavior of the predicates, p%4i%*, appearing in conditional exressions
such that instead of testing for the values %3T%* and %3NIL%* we
test only for %3NIL%* and non-%3NIL%*. That is, anything other than %3NIL%*
satisfies the p%4i%*. This allows such coding tricks as:
.BEGIN SELECT 3;TABIT1(30);TURN OFF "←";
\[x ← cdr[x] → ...]
%1which is equivalent to:%*
\x ← cdr[x];
\[not[null[x]] → ...]
.SELECT 1;
(Recall that the value of "←" is the value of the RHS.)
.END
As with most coding tricks, they should be avoided like the plague.
Again, please note that this discussion is not a change to our definition
of conditional expression, but an implementation dependent feature.
.<<pic of NIL>>
.SKIP TO COLUMN 1;
.SS(A picture of the atom %3NIL%*,%3NIL%*)
We have been writing the atom %3NIL%* as:
.GROUP SKIP 12;
Where the atoms for %3PNAME%* and %3VALUE%* are represented as:
.GROUP SKIP 12;
More realistically we should represent %3NIL%* as:
.NEXT PAGE;
.SS(A first look at %3cons%1)
%1
The effect of the ⊗→%3cons%*↔← function is quite different from that
of the other primitive LISP functions. The other functions (or
predicates) manipulate existing Sexpressions, whereas %3cons%*
must construct a new sexpression from two existing sexprs.
That is, given representations of two sexprs, say %3x%* and %3y, cons[x;y]%*
is to get a new cell, put the representation of %3x%* in the %3car%*-part of
the cell and the representation of %3y%* in the %3cdr%*-part:
.BEGIN TURN ON "\";NOFILL;TABS 10,30,45;
.GROUP
result of %3cons[x;y]%*
\\%7[~~~~~][~~~~~]
\ %1rep. of %3x\\ %1rep. of %3y%1
.APART
.END
Where is %3cons%* to obtain these new cells? This is accomplished by the ⊗→free
storage area↔←. Within the free storage (FS) area resides all the cell
which have a %3car%*- and %3cdr%*- part. The cells which contain the actual
p-names we know reside in the full word space (FWS). At any point
in a LISP computation there are cells in the FS are which do not contain
any parts of the user's computation. In particular, when the computation
is begun, only the atom structure for the initial LISP symbol table
uses cells in the FS area. The remaining FS cells form a %2free-space list.%*
Whenever a %3cons%* needs a cell the first cell in the FS list is used and
the FS list is set to the %3cdr%* of the FS list.
As the computation continues, more and more cell are taken from the FS list.
When a %3cons%* operation asks for a cell and the FS list is empty, the
computation is suspended and the %2⊗→storage reclaimer↔←%* or %2⊗→garbage collector↔←%* is
called.
.SS(Garbage collection,garbage collection)
During the course of a computation, contents of cells which were taken
from the FS list often become unnecessary. For example during the evaluation
of something as simple as:
←%3(CONS (QUOTE A)(QUOTE B)),%* many cells are used:
%21.%* At least seven cells are needed just to read in the expression.
If some of the atoms are not present in the symbol table,
more cells will be needed.
%22.%* One cell will be needed to perform the %3cons%* operation.
After the computation is completed, none of the eight mentioned cells are needed.
They are garbage.
Why not simply return these `garbage cells' explicitly to the FS list?
Frequently it is very difficult to know just exactly which cells
%6are%* garbage. Indeed, experiments have been performed in which LISP
programmers were allowed to return `garbage' to the FS list themselves.
The results were disastrous; list structure, thought to be garbage
was returned to the FS list by the programmers, unaware it was still being
used by other computations. We will see where these difficulties arise
later.
Thus reclamation is passed to the LISP system. The %3cons%* function and
its FW space counterpart, %3fwcons%*, are the only functions allowed
to mainpulate the free storage lists. When either list becomes empty, the
garbage collector is called.
%2←The fundamental assumption behind garbage collection is:%*
.NARROW 10,10;
At any point in a LISP computation, all cells which contain
parts of the computation are reachable (by %3car-cdr%* chains)
through a fixed set of known cells or registers.
.WIDEN;
The first phase of the garbage collector, called the %2⊗→marking phase↔←%*,
marks all of the list structure which is currently active (reachable
through the above mentioned fixed cells). This should include all the
atoms in the symbol table and all the cells reachable by %3car-cdr%* chains
from any of these atoms. Also any partial computations which have been
generated must also be marked. Once all the active structure has been
marked, we proceed to the second phase, the %2⊗→sweep phase↔←.%*
Once the marking has been completed, we go linearly (sweep) through memory,
collecting all those cells which have not been marked. Again,
the assumption is that if cells are not marked in the first phase,
then they do not contain information necessary to the LISP computation.
These unmarked cells are chained together via their %3cdr%*-parts to form
a new FS list. The FS pointer is set to the beginning of this list;
similarly, the unmarked cells in FWS comprise the new FW list.
A more detailed discussion of this garbage collector
will be given when examine the details of implementation in {yonss(P26)}.
And a more complex algorithm is discussed in {yonss(P27)}.
Garbage collection appears to be a very complex and time-consuming
process. Indeed it is. As indicated above, there are alternatives in some
applications. If the data-structure manipulations are particularly simple
then leaving storage management in the programmer's hands might
suffice. However, LISP generates very intertwined structures.
Perhaps there is
another way to allow the system to handle storage management.
First notice that storage management becomes quite simple if there is no sharing
of sublists. The question of when to return a list to the free space list
is easily solved. However it is desirable to share substructure quite often.
Instead of using a garbage collector, we might associate a counter, called
a %2⊗→reference counter↔←%*, with each
list when it is built. In that counter we will store the number of references
to that list. Thus the counter will be initialized to 1 when the list is created.
Whenever the list
is shared we increase the counter by 1; whenever the list is no longer to
be shared by some list we decrease the counter by 1.
When the count goes to 0 we can put the cells of the list in the free space list.
One of the most glaring defects in this reference counter scheme is the
prohibition of circular lists. Consider the following sequence:
.BEGIN NOFILL;GROUP;TURN OFF"←";
%21.%* Manufacture a list,%3x%*: %3x ← (B I G M O T H E R L I S T)%1. Reference count is 1.
%22.%* Circularize it: %3x ← circle[x];%*. Reference count is now 2.
%23.%* Delete all references to %3x%*: %3x ← NIL%*. Reference count reverts to 1,
but the list is not referred to, is not on the free space list, and has thus
been lost to the system.
.END
.CENT(A simple LISP garbage collector written in LISP)
We will now write a garbage collector in LISP to mark and sweep nodes
in FS and FWS.
It will have three main functions:
.BEGIN INDENT 0,10;
%3initialize[x;y]%* to initialize the marking device for each cell in the space from
%3x%* to %3y%*.
%3mark[l]%* to do the actual marking of a list %3l%*.
%3sweep[x;y]%* to collect all inaccessible cells in the space delimited
by %3x%* and %3y%*.
%3initialize%* will be called twice; once for FS and once for FWS.
%3mark%* will be called for each base register which points to
active (binary) list structure.
The basic structure of the marker is: if the word is in FWS mark it and leave;
if the word has already been marked simply leave. Otherwise the word is
in FS and thus has a %3car%* and a %3cdr%*; mark the word; mark the %3car%*;
mark the %3cdr%*. The marker is thus recursive; all of the stack manipulation
done by the AMBIT program will be hidden by the recursion.
%3sweep%* will be called twice; once to generate a new free space list and once
to generate a new full word space list. Elements of these free
lists will be chained together by their %3cdr%* parts.
The initialization and sweep phases of this garbage collector are very similar;
both phases must be assured of reaching every node in the space. We used the
%3down%*-arrows for this.
.END
These main functions use several other functions and predicates:
.BEGIN INDENT 0,10;
%3fwswrdp[x]%* is true just in the case that %3x%* is a word in FWS. This is
used as one of the termination conditions of %3mark%*.
%3makeA[x]%* marks word %3x%* as accessible.
%3makeNA[x]%* marks word %3x%* as not accessible.
%3NAp[x]%* is true if word %3x%* is not accessible.
%3down[x]%* follows the "down" link of the node %3x%*.
%3conca[x;y]%* attaches node %3x%* to the front of the list %3y%*.
The value returned is the new list.
%3conca%*
is easily described in AMBIT. Can you write %3conca%* as a LISP function?
.END
.BEGIN; CENTERIT;GROUP;SELECT 2;
.GROUP SKIP 7;
←AMBIT diagam for %3conca%*.
.END
.BEGIN SELECT 3;TABIT2(18,20);TURN OFF "←";
initialize <= λ[[x;y]
\prog[[]
\ a\makeNA[x];
\\x ← down[x];
\\[eq[x;y] → return[T]]
\\go [a]]]
.APART;
.GROUP;
mark <= λ[[l] [\not[NAp[l]] → T;
\fwswrdp[l] → makeA[l];
\T → makeA[l];mark[car[l]];mark[cdr[l]] ]]
.APART
.GROUP
sweep <= λ[[x;y]
\prog[[z]
\ a\[NAp[x] → z← conca[ x;z]];
\\x ← down[x];
\\[eq[x;y] → return [z]];
\\go[a]]]
.END
.CENT(A link-bending garbage collector for LISP)
***FIXUP can it, or move to storage and efficieny***
The description of this very simple collector is easily understood either as
a LISP function or as an AMBIT program. The collector we are about to describe
is more naturally described graphically. First notice that the AMBIT program
uses an explicit stack to store traversing information whereas in the LISP
description the use of a stack is implicit in the recursion of %3mark%*.
The use of a stack is one of the difficulties associated with this simple
collector. Garbage collection is invoked when available space has become
exhausted, but here we are, asking for %2more%* space to use for stacking.
The usual solution is to allocate a separate area for stack storage. This
has its drawbacks. If we don't allocate enough stack space, i.e., if the
depth of a piece of structure becomes too great, then the marker will fail.
Notice to that the amount of stack space can become large; proportional to the
length of a list.
.GROUP SKIP 8;
Another means of dispensing with a stack when traversing a tree is to
use a more complicated representation for each node. Notice that
if we examined "snapshots" of the execution of the traversal of a tree
as long as we traversed the tree each time in the same order, the contents
of the stack would be identical ⊗↓except for perhaps the actual machine locations
used in the stack←. Instead of replicating this portion of a stack on each
traversal we could save the stack information with the nodes in the tree.
This technique is called ⊗→threading↔← ⊗↓See Knuth's Kompendium←.
Threading complicated the representation and causes some difficulties when
we wish to store list-structure rather than trees. However the idea
of dispensing with the stack %2is%* worthwhile.
We can strike a comproimise. Instead of permanently storing
the threads in the structure we can modify the structure as we traverse it,
use the threads to mark, and then to restore the structure to its original
topology.
Certainly the marker will be more complicated, but the complication is
not insurmountable. In fact, it is even reasonably straightforward to prove
the correctness of such an algorithm ⊗↓ W. deRoever, private communication.←.
Finally, here is such a "link-bending" marker written in AMBIT/G:
.NEXT PAGE;
To reinforce ideas, here is a simple data graph and a sketch of the
modifications to it as the marker operates:
.CENT(Problems)
I This problem deals with what is known in LISP as %2⊗→hash consing↔←%*.
We have been storing atoms uniquely, but it should be clear from the behavior
of %3cons%* that non-atomic sexprs are %2not%* stored uniquely.
Certainly storing single copies of any sexpr would save space. For example,
the non-atomic structure of
%3((A . B).(A . B))%* could be represented with two cells rather than three.
Unique storage is not without its difficulties. What problems do you forsee
in implementing such a scheme?
II We said on {yon(P48)} that many LISP computations generate list structure
rather than true binary trees? Give an example.
.P55:
II Can you write a LISP function %3circle <= λ[[x] ... %* which will take
a list %3x%* and make it circular. Thus:
.BEGIN TABS 8,30,47,65;NOFILL;TURN ON "\";GROUP;
%7
\[~~~~~~~[~~~]\[~~~]~~~]\[~~]~~~]\[~~~~]~~~]
%3\NOTHING\ CAN\ GO\ WRONG
.END
This list is circular on its "last two" elements.
Needless to say printing such structures is not appreciated.
.SS(%3read%* and %3print%*,,P13:)
.TURN ON "←";
When you begin to implement LISP you find that a very significant
part of LISP can be written in LISP. We have already seen that the
evaluation process is expressible this way.
Here we will see that the majority of the I/O routines can be
written as LISP functions calling a very few primitive routines.
The primitive routines can also be described in `pseudo-LISP'.
That is, we will give a LISP-like description of them, though
they would normally be coded in machine language.
The primitive functions are ⊗→%3ratom%*↔← (read an atom) and ⊗→%3prin1%*↔←.
.BEGIN INDENT 0,10;
.GROUP
%3ratom[ ]%* is a function of no arguments. It reads the next atom
or special character (left paren, right paren or dot).
It looks up that object in the symbol table and returns
a pointer to that symbol table entry. If no entry
is found an appropriate entry is made.
%3ratom%* is the LISP ⊗→scanner↔←. %3ratom%* flushes spaces and commas,
using them only for delimiters. It returns only atoms or special characters
to %3read%*, the LISP ⊗→parser↔←.
.APART
.GROUP
%3prin1[x]%* is a function of one argument expecting an atom, left paren
right paren, blank, or dot as the value of its argument.
It will print the p-name of that object on the output
device.
.APART
.END
To make life simpler we need to be able to refer to atoms whose values are
the characters "%3)%*", "%3(%*", ".", and " "(blank).
We will assume that ⊗→%3rpar%*↔←, ⊗→%3lpar%*↔←,
⊗→%3period%*↔←, and ⊗→%3blank%*↔← are such atoms. For example, if the next input
character is "(" then
←%3eq[ratom[ ];lpar]%* is true (and the input pointer is moved to
the next character!).
%3prin1[period]%* will have the effect of printing a %2"."%* on the output
device.
We will discuss the structure of %3ratom%* and %3prin1%* in a moment. In
the meantime here are %3read%* and %3print%*:
.BEGIN TABIT2(17,20);TURN OFF"←";SELECT 3;
.GROUP
⊗→%3read%*↔← <=λ[[ ]prog[[j]
\j ← ratom[ ];
\[eq[j;lpar] → return[read1[ ]];
\ or[eq[j;rpar];eq[j;period]] → LOSEBIG1;
\ T → return[j]]]]
.APART
.GROUP
⊗→%3read1%*↔← <= λ[[ ]prog[[j;k]
\\j ← ratom[ ];
\\[eq[j;lpar] → return[cons[read1[ ];read1[ ]]];
\\ eq[j;rpar] → return[NIL];
\\ eq[j;period] → go[rd];
\\ T → return[cons[j;read1[ ]]] ];
\rd\k ← ratom[ ];
\\[eq[k;lpar] → k ← read1[ ];
\\ or[eq[k;rpar];eq[k;period]] → LOSEBIG2];
\\j ← ratom[ ];
\\[eq[j;rpar] → return[k];
\\ T → LOSEBIG3] ]]
.APART
.END
Here's %3print%* and friends. %3terpri%* gets a new output line.
(note: the value of %3print[x]%* is %3x%*.)
.BEGIN TABIT2(17,20);TURN OFF "←";SELECT 3;
.GROUP
⊗→%3print%*↔← <= λ[[x]prog[[ ]
\prin0[x];
\terpri[ ];
\return[x]]]
.APART
.GROUP
⊗→%3prin0%*↔← <= λ[[x]prog[[j]
\\[atom[x] → return[prin1[x]]];
\\j ← x;
\a3\prin0[car[j]];
\\[null[cdr[j]] → go[a6]]
\\prin1[blank];
\\[atom[cdr[j]] → go [p1]];
\\j ← cdr[j];
\\go[a3];
\p1\prin1[period];
\\prin1[blank];
\\prin1[cdr[j]];
\a6\prin1[rpar];
\\return[x] ]]
.APART
.END
So far we have thrown all the I/O back on %3ratom%* and %3prin1%*. Clearly
%3ratom%* will be more interesting. All %3prin1%* need do is get the p-name and
print it. %3ratom%* needs to search the symbol table (efficiently hopefully),
and if
the atom is not found, add it to the table. All %3ratom%* has to work
with is the actual character string (called %3chr-str%* in the future) which
will be the p-name of some atom. What %3ratom%* could do is look at the
p-name of each atom currently in the symbol table; when it finds a match
it returns a pointer to the beginning of that atom.
(Notice this is essentially the search scheme of %3assoc%*.)
If the appropriate
atom is not found it can build a new one consiting of the p-name, add it
to the table, and return a pointer to this new atom. This would
have the appropriate effect; each atom would be stored uniquely, but
the efficiency would leave something to be desired.
.CENT(Problem)
***** non-recursive reader...better worse***
*** slashifying ***
.SS(Hashing,hashing,P14:)
Symbol table lookup is exactly the problem of looking up
words in a dictionary. The above scheme of %3assoc%*
⊗↓called linear or lexicographical search←
is analogous to a person beginning at page one of the dictionary and
proceeding linearly (page-by-page and word-by-word) through
the book until he found the word in question. Truly a losing
scheme. What we normally do is look at the first character of
the word and go immediately to the subsection of the dictionary which
has the words beginning with that character. We know that if
we cannot find the defintion of our word in that subsection we need
look no further in the book. Usually we delimit our search even
further by keying on subsequent characters in the word. Finally
we may resort to linear search to pin down the word on a specific
page or column.
What we want is a similar scheme for the machine. We might in fact
mimic the dictionary search, subdividing our table into 26 subsections.
We can do better.
Since it is the machine which will subdivide and
index into the symbol table, we can pick a scheme which is computationally
convenient for the machine. Besides being convenient, the scheme should
result in rather even distribution of atoms in the subsections.
Obviously if the majority of the atoms end up in the same partition
of the table we will have gained little towards improving the
search efficiency. Now for terminology. Each of the partitions
or subdivisions of the table is called a %2⊗→bucket↔←%*. Each atom will
appear in at most one bucket. The computational scheme or function
used to determine which bucket a particular atom belongs in is called
a %2⊗→hashing function↔←%*. All ⊗→%3ratom%*↔← has to work with is %3chr-str%*, the
encoding of the actual name of the atom. So the hashing function
will use %3chr-str%* to determine which bucket to examine. If the atom
with ⊗→PNAME↔← %3chr-str%* does not appear in that bucket we are assured
that it does not appear anywhere in the table. In this case we
make up the minimal table entry --#atom#indicator, %3PNAME%*, p-name structure#--
and add it to that bucket.
There are lots of hashing functions. Here's one:
%21.%* Assume that we have N+1 buckets, numbered 0, 1, 2 ... N.
%22.%* Take the representation of %3chr-str%* (it's a number) and
divide it by N+1.
%23.%* Look at the remainder. It's a number between 0 and N.
%24.%* Use that remainder as the index to the appropriate bucket.
This is a scheme frequently used in LISP. Given the bucket number,
we then run down the list of atoms in that bucket, comparing
print-names against %3chr-str%*. If the atom is not found, %3cons%*-up
the atom and stick it in the bucket.
There is a lot of mystery and history about hashing and other means
of searching and storing in symbols. References are given in the
bibliography.
In review, here is the structure of the LISP input mechanism:
%21.%* %3read%*, the LISP ⊗→parser↔←, builds a list-structure representation
of the input string. %3read%* is defined in terms of %3ratom%*.
%22.%* %3ratom%*, the LISP ⊗→scanner↔←, builds atoms and special characters
from the input. It searchs and increments the LISP symbol table.
%23.%* The LISP symbol table, usually called ⊗→%3OBLIST%*↔← (for %2⊗→object list↔←%*),
is a list of buckets. Each bucket is a list of the atoms which `hash' to that bucket.
We actually represent the object list as an array named %3oblist%*.
This way the hash number will give us the array subscript and we can
go to the right bucket immediately.
We won't have to go "cdr-ing" down the object list to get to the right bucket.
See figure on next page.
Here is a `pseudo-LISP' version of ⊗→%3ratom%*↔←:
.BEGIN TABIT2(17,20);FILL;
%3hash%*\is a function returning the bucket number of its argument.
%3insert%*\is a function to build the atom and insert it into to bucket.
%3right-one%*\is a predicate used to check if an atom
has the right print-name.
.NOFILL
.TURN OFF "←";
.SELECT 3;
⊗→ratom↔← <= λ[[ ]prog[[z;i;bucket]
\\i ← hash[chr-str];
\\bucket ← oblist[i];
\a\[null[bucket] → return[insert[chr-str]]];
\\z ← get[car[bucket];PNAME];
\\[right-one[z;chr-str] → return[car[bucket]]];
\\bucket ← cdr[bucket];
\\go[a]]]
.END
%3get%* is a LISP system function. It is described on {yon(P52)}.
.SKIP TO COLUMN 1;
.SS(A review of the structure of the LISP machine,LISP machine)
.BEGIN TABIT2(10,20);GROUP;
\_______________________________________
\\⊗→%3eval%*↔← and friends
\\⊗→%3read%*↔← and ⊗→%3print%*↔←
\\the ⊗→garbage collector↔←
\\the base registers for marking
\\ ⊗→FS pointer↔←
\\ ⊗→FWS pointer↔←
\\ symbol table(⊗→%3OBLIST%*↔←) pointer
\\ registers for partial results
\_______________________________________
\\⊗→Free space↔←
\\ the free space list
\\ those parts of sexprs containing
\\ %3car%*- and %3cdr%*-parts.
\_______________________________________
\\⊗→Full word space↔←
\\ the full word space list
\\ atom print names
\\ numbers
\_______________________________________
.END
.NEXT PAGE;
.SS(Binding revisited,bind,P78:)
The most interesting changes in the evaluator involve binding
and unbinding of variables.
We have seen that the old symbol table mechanism has the correct
effect for the proper evaluation of recursive functions. As
we bound variables to values on entry to a λ-expression, we
%3cons%*ed the new bindings onto the front of the symbol table. This
had two results:
%21.%* In the evaluation of the body of the λ-expression we got the
correct bindings of the variables.
%22.%* The old value was saved so that we could retrieve it on leaving
the λ-body.
Now with the new table organization we need to develop the same
facility. It is not sufficient for the binding of λ-variables to
simply change the contents of the ⊗→%3VALUE%*-cell↔←. This would violate
condition %22%*. Besides changing the value, we must save the prior
value.
The crucial phrases are lines 14 and 16 in the new version of %3apply%*.
⊗→%3bind%*↔← is a function, taking two arguments. The first is the list of
λ-variables; the second is the list of new values. %3bind%* saves the
old values and rebinds the λ-variables to the new values.
⊗→%3unbind%*↔← is a function of no arguments used to restore a list
of λ-variables to their previous values. How is
this wonderous feat performed?
We have a ⊗→stack↔←, or ⊗→pushdown-list↔←, called SP
(for %2S%*pecial %2P%*ushdown) in which we can
save old values of variables. %3bind%* will add values to SP; %3unbind%*
restores the saved values. Actually because of the stack-like
behavior of the binding and unbinding processes we can increase
the efficiency of %3bind%* and %3unbind%*. %3bind%* saves both the value
and the location of the %3VALUE%*-cell for each variable being rebound.
It also puts special marks in the SP stack delimiting each block
of λ-rebindings. All %3unbind%* need do is restore the first block
of saved values. It knows the values and also knows the addresses of
the %3VALUE%*-cells.
All of the information it needed for restoration is saved in the stack.
.BEGIN GROUP;TABIT3(30,45,60);
Given %1λ[[x%41%*; ...; x%4n%*]%9x%1][a%41%*; ... ;a%4n%*], here's an example of binding:
\ to value\\old value of x%41%*
\ cell for x%41%*
\save
\and\ ...
\rebind
\ ===>
\ to value\\old value of x%4n%*
\ cell for x%4n%*
\\ |
\\ ↓
\\rebind x%4i%* to a%4i%*, changing the
\\ contents of the value cell
\\ (see %3*bind%*)
\\ |
\\ ↓
\\ evaluate %9x%*
\\ |
\\ ↓
\\restore old values using information
\\ stored in satck, SP.
\\ (see %3*unbind%*)
.END
.BEGIN CENTERIT;
.GROUP SKIP 15;
←%2The primitives, %3*bind%* and %3*unbind%*.
.END
This binding scheme, called %2⊗→shallow binding↔←%* works quite well for
simple λ-binding and lookup.
*****bridge it***
A variable used globally (or free) in a function (or %3prog%*) is one which
does not appear in the λ-list or in the list of %3prog%*-variables.
For example in:
←%3λ[[x]*[x;y]], y%* is global.
Communication of global variables between interpreted functions
is not problematic: just look down the atom structure for the %3VALUE%*-cell.
Handling of global variables by compiled functions requires some
care. The ⊗→%3VALUE%*-cell↔← mechanism is designed to accomplish this.
Essentially, the %3VALUE%*-cell will %2always%* contain the current value
of its variable. The compiler then needs to be able to find this cell and
generate efficient code to manipulate its contents.
As with the previous a-list symbol table
we need exercise some care when handling functional arguments. How can we
implement the equivalent of the %3FUNARG%* hack in this new binding and symbol table
organization? Recall how the old %3eval%* coped ({yon(P79)}).
When we recognized an instance of a functional argument we saved a pointer to
the current environment. When we %2applied%*
the functional argument we restored the symbol table in such a way
that global variables were accessed in the saved environment while
local variables were found in the current environment.
We must do the same. When %3function%* is seen save the current SP pointer;
when we apply the functional argument,
.BEGIN centerit;
%3←(FUNARG %*<function> <old SP>%*) %1to arg%41%*; ... arg%4n%3 ,
.END
we will first rebind all of the variables found by the old SP pointer to
those old values, while saving the current values in SP. Then we can rebind the
λ-variables (i.e., local variables) of the <function> to arg%41%* through
arg%4n%*. The environment will then be properly restored for evaluation of the
function body. When the evaluation has been completed we restore using %3unbind%*.
Compare the shallow binding strategy to that of the a-list. The a-list was always
explicit when evaluation was occurring; saving environments only required saving
a pointer to the current symbol table; changing environments at most required
calling %3eval%* with a different symbol table, and when leaving a context
the old table was restored implicitly by the recursion mechanism. Accessing
a variable involved an appreciable computation; we had to search the table
for the variable-value pair.
Shallow binding obviates the symbol table search while incurring added
expense in binding and unbinding.
The care and feeding of functional arguments is more difficult since there
is only one symbol table, not the tree of tables implicit in the
previous incarnation. True, the information necessary to recover an environment
is present in SP, but it is expensive to retrieve it.
*****SHOW PROBLEMS WITH FUNCTIONAL VALUES****
Shallow binding: 0; a-list: 1; (Christians: 0; lions: 1).
There is an
alternative binding strategy called %2⊗→deep binding↔←%*.
We will also present an alternative calling structure
which works well with deep bindings and is not so hardware
oriented as its shallow competitor.
These alternatives are perhaps more intuitive implementations our original a-list
version of %3eval%* than is the shallow binding scheme. We will contrast their
relative efficiencies.
.SS(Macros and special forms,macros,P18:)
Most of the discussion to this point has dealt with getting
a new efficient symbol table which can fulfill our requirements
of permanence and multiplicity of properties. Little has been said
about user controlled function calling, which we called the desire for
generality. Before introducing the definition of the new evaluator
we shall deal with that aspect.
Recall our discussion of ⊗→special forms↔← in {yonss(P8}).
Special forms have been used for two purposes: to control the evaluation
of arguments (conditional expressions, quoted expressions,
%3and, or%*, etc.), and to create the effect of functions with an indefinite
number of arguments (%3list, append, plus, ...%*)
Frequently this second application of special forms can be improved upon,
particularly in the presence of a compiler.
Describing such functions as special forms is sufficient,
but not efficient, since the body of the definition must
contain explicit calls on %3eval%*. Even though we wish to define
some functions as if they had an arbitrary number of arguments, when
we %6use%* (i.e. call) the function, the number of arguments to be
applied %6is%* known. In particular, when the compiler is examining the
program, the number of arguments is known. Hopefully the compiler can be
made smart enough to compile better code than calls on %3eval%*.
That hope is well-founded.
Assume, for example, we wish to define %3plus%* as a function with
an indefinite number of arguments:
.BEGIN CENTERIT;SELECT 3;GROUP;
←plus[4;5] = 9
←plus[4;5;6] = 15
←plus[4;add1[2];4] = 11
.END
That is %3plus%* to have the properties of a function: its arguments
are to be evaluated (from left to right); but it can take an arbitrary number.
What is needed here seems clear: define %3plus%* in terms of a %2binary%*
addition function, %3*plus%*.
.BEGIN CENTERIT;SELECT 3;GROUP;
←plus[4;5] = *plus[4;5] = 9
←plus[4;5;6] = *plus[4;*plus[5;6]] = 15
←plus[4;add1[2];4] = *plus[4;*plus[add1[2];4]] = 11
.END
That is, we %2expand%* calls on %3plus%* into a composition of calls on
%3*plus%*.
%3plus%* is being used as a %2macro%* and the expansion process in terms
of %3*plus%* is called %2macro expansion%*. Notice that is macro expansion
can be done by a compiler, generating a sequence of calls on %3*plus%*.
Realize too, that since LISP programs must perform equivalently when
interpreted, we must recognize a macro construction inside %3eval%*.
How are macros written and how do they work? The body of a macro is a
λ-expression of %2one%* argument. The %2use%* of a macro looks just like
an ordinary function call, but what is bound to the λ-variable is the whole
call on the macro. When you look at the evaluation mechanism for
macros in the %aSM%*-%3eval%* you will see that the result of the macro
expansion is passed to %3eval%*. Thus the task of the macro body is to
expand the macro call and return this expansion as its value.
The task of the compiler will be quite similar; it will expand the macro
but instead of evaluating the expansion it must %2compile%* it.
.BEGIN TURN ON "#";
Let's define %3<%4m%*=%1 to mean "#is#defined#to#be#the#macro#...".
Then a simple macro definition of %3plus%* might be:
.END
.BEGIN SELECT 3;TABIT2(10,25);GROUP;
.P58:
\plus <%4m%*= λ[[l]\[eq[length[l];3] → cons[*PLUS;cdr[l]]
\\ T → list[*PLUS;cadr[l];cons[PLUS;cddr[l]]]] ]
.END
Thus a call %3(PLUS 3 4 5)%* would bind %3l%* to %3(PLUS 3 4 5)%* and
the evaluation of the body would result in %3(*PLUS 3 (PLUS 4 5))%*.
Evaluation of this expression would result in another call on the macro.
This time %3l%* would be bound to %3(PLUS 4 5)%*. Now
%3eq[length[l];3]%* %2is%* true and the value returned is %3(*PLUS 4 5)%*.
This can be evaluated, giving 9, and finally the outermost call on %3*PLUS%*
has all its arguments evaluated, and we get the final answer, 12.
This is a very simple (and inefficient) macro definition. Since the body
of a macro has available all of the evaluation mechanism of LISP, and
since the program structure of LISP is also the data structure, we can
perform arbitrary computations inside the expansion of the macro. Truly
LISP macros have the power to cloud men's minds!!!
****GIVE BETTER VERSION OF PLUS****
Notice that %3SETQ%* can easily be defined as a macro
over %3SET%*:
.BEGIN CENTERIT;SELECT 3;GROUP;
←setq <%4m%*= λ[[m] list[SET;list[QUOTE;cadr[l]];caddr[l]]].
.END
.P54:
The effect of "<%4m%*=" should be clear:
it puts the body of the macro definition on the property-list of the macro
name under the indicator, %3MACRO%*. Likewise "<=" puts the function body
on the p-list under the indicator, %3EXPR%*. Similarly, we will define
"<%4f%*=" to mean "..is defined to be a special form..." and whose effect
is to put the body under the indicator, %3FEXPR%*. The body of a fexpr
definition is a λ-expression of (usually) a single λ-variable, say %3l%*. When the
fexpr is called we bind the list of %2unevaluated%* arguments to %3l%*.
Thus we could define %3plus%* by:
.BEGIN SELECT 3; GROUP;TABIT2(10,12);turn off "←";
.P59:
plus <%4f%*= λ[\[l] prog[[sum]
\\sum ← 0;
\a\[null[l] → return[sum]];
\\sum ← *plus[sum;eval[car[l]]];
\\l ← cdr[l];
\\go[a]]]
.END
Or %3and%* could be defined as:
.BEGIN SELECT 3;CENTERIT;GROUP;TABIT2(20,35);
←and <%4f%*= λ[[l]evand[l]]%1
where %3evand%* is defined as:
%3
\evand <= λ[[l][\null[l] → T;
\\eval[car[l]] → evand[cdr[l]];
\\T → NIL]]
%*
.END
Notice that this definition of %3evand%1 differs from the one on
{yon(P53)}. The earlier definition required an explicit symbol table;
the newer one uses the global table. This is a mixed blessing. As usual
there are difficulties in getting the correct bindings of variables.
Most applications of %3FEXPR%*s involve explicit calls on %3eval%*
within the body of the %3FEXPR%*.
Consider the following sequence :
.BEGIN TABIT2(20,37);SELECT 3;TURN OFF "←";GROUP;
\wrong <%4f%*= λ[[x] prog[[y]
\\y ← 2;
\\return[eval[car[x]]]]
\y ← 0;
\wrong[y];
.END;
Execution of the above sequence show the value of %3wrong[y]%* to be %32%*,
rather than the expected %30%*. Clearly, the problem is that the call on
%3eval%* takes place in the wrong environment. To alleviate this situation
%3FEXPR%*s may be defined with %2two%* arguments. In this case a %2call%*
on the %3FEXPR%* will bind the environment %2at the point of call%* to that
second argument. %3eval%*,and %3apply%* are allowed to be called with either
one or two arguments. If a second argument is present, it is used as the
environment during evaluation.
Thus:
.BEGIN TABIT2(20,39);SELECT 3;TURN OFF "←";GROUP;
\right <%4f%*= λ[[x;a] prog[[y]
\\y ← 2;
\\return[eval[car[x];a]]]
\y ← 0;
\right[y];
.END;
The call on %3right%* will use the environment with %3y%* being %30%*
rather than %32%*.
Macros can be used to perform the operations which special forms
do, but with perhaps more efficiency.
The idea of macro processing is not recent. Some of the earliest assemblers
had extensive macro facilities. Lately macros have been used as a means
of extending so-called high level languages.
One of the most simple kinds of macros is %2textual substitution%*.
That is, when a use of a macro is detected we simply replace the call by its
body. A slightly more sophisticated application is the %2syntax macro%*.
Everytime we come across an application of a syntax macro the expander
processes it as if it had never been seen before even though much
of the expansion is repetitious. That is, syntax macros have no memory.
%2computational macros%* are an attempt to reduce some of this repetition.
In this scheme a certain amount of processing is done at the time the macro
is %2defined%*. For example a computational subtree reflecting the body of the
macro might be formed. Then whenever the macro is %2used%* we can
simply make a copy of this subtree and "glue" this subtree into the parse-tree
which we are building. This computational subtree is commonly formed by passing
the body of the macro through the compiler in a
"funny" way. The main problem with the computational macro is that there are
many desirable macros which have no such subtree, or there is other information
necessary to process the macro. There are solutions to this problem,
one of which closely parallels the abstract syntax ideas of McCarthy.
All of these styles of macros are subsets of the LISP macros.
*****MORE HERE ON A.D.S. AND MACROS******
Many versions of LISP also have a very simple syntax macro (called ⊗→%3read%* macros↔←)
independent of
the <%4m%*= - facility. Constants appear quite frequently in LISP expressions;
and so we have already introduced abbreviations for the sexpression
representation of numbers, %3T%* and %3NIL%*. That is we don't %3QUOTE%* them.
%3read%* macros are used to abbreviate other sexpressions. The most
common %3read%* macro is used to abbreviate the construct:
.TURN ON "←";
←%3(QUOTE %*<sexpression>%3)%*.
A special character is chosen to designate the macro, say "@". Then
then whenever %3read%* sees "@" the next sexpression, s, is read in and
the value: %3(QUOTE %1s%*)%1 is returned by %3read%*. Thus:
←@<sexpression> is an abbreviation for %3(QUOTE <sexpression>).%1
In some systems the user may define his own %3read%* macros, in others
they are pre-defined.
.CENT(Problems)
I. Define %3list%* and %3append%* as macros. You may use only
the LISP primitives (functions, predicates, conditionals and
recursion) and a binary function, %3*append%*.
II. Give a macro definition of an extended %3SETQ%*, which is called
as %3(SETQ#%1var%41%*#exp%41%*#...#var%4n%*#exp%4n%3)%1.
Each var%4i%* is a name; each exp%4i%* is an expression to be evaluated
and assigned to var%4i%1. The assignments should go from "left-to-right".
Thus %3(SETQ X 2 Y (TIMES 2 X) X 3)%* when executed should assign
%33%* to %3X%* and %34%* to %3Y%*.
III. Define %3list%* as a special form.
.SS(%aSM%*-%3eval%*,%3eval%*,P30:)
Finally, here is the new evaluator.
(the `line numbers' are not part of the definitions)
.BEGIN VERBATIM;SELECT 3;
eval <=
1. λ[[x]prog[[y]
2. return[[numberp[x] → x;
3. atom[x] → [y ← get[car[x];VALUE] → cdr[y]]
T → err[UNBOUND VARIABLE]];
4. atom[car[x]] → [y ← getl[car[x];(EXPR FEXPR MACRO)]
5. → [eq[car[y];EXPR] → apply[cadr[y];mapcar[function[eval];cdr[x]]];
6. eq[car[y];FEXPR] → apply[cadr[y];list[cdr[x]]];
7. T → eval[apply[cadr[y];list[x]]]];
8. y ← get[car[x];VALUE] → eval[cons[cdr[y];cdr[x]]];
9. T → err[UNDEFINED FUNCTION]];
10. T → apply[car[x];mapcar[function[eval];cdr[x]]]]]]]
apply <=
λ[[fn;args]
11. [atom[fn] → [get[fn;EXPR] → apply[get[fn;EXPR];args];
12. T → apply[eval[fn];args]];
13. eq[car[fn;LAMBDA] → prog[[z]
14. bind[cadr[fn];args];
15. z ← eval[caddr[fn]];
16. unbind[];
17. return[z]];
18. T → apply[eval[fn];args] ]]
.END;
First let's describe the new LISP system functions which are used here.
They are:
.BEGIN INDENT 0,10;
.p52:
%3get[x;y]: %*
%3x%* is an atom; %3y%* is an indicator. ⊗→%3get%*↔← will return the value-part
of the attribute-value pair
associated with %3y%* under the atom %3x%*. If %3x%* does not have the
indicator %3y%*, then %3NIL%* is returned.
.END
.BEGIN INDENT 0,10;
%3getl[x;y]:%*
%3x%* is an atom; %3y%* is a list of indicators (see line 4). ⊗→%3getl%*↔←
will search the property list of the atom %3x%* for the first occurrence
of an indicator which appears in the list %3y%*. If such a match
is found, then the remainder of the p-list, beginning with the
matching indicator, is returned. If no match is found, %3NIL%* is
returned.
.END
.BEGIN CENTERIT;GROUP;
An example:
.GROUP SKIP 6;
←%3getl[FOO;(BAZ PNAME)]%* has value: %3get[FOO;PNAME]%* has value:
.END
The virtue of %3getl%* is that it can distinguish between an atom which has
an indicator with value %3NIL%* and an atom which does not have the indicator.
%3get%* cannot communicate this distinction.
First, on lines 5 and 10 we use the LISP mapping function, %3mapcar%*, to evaluate the argument
list during function calls. See {yon(P34)}.
Notice line %33.%* is an application of an obscene LISP coding trick
described on {yon(P28)}. Notice too, that line %33%* uses %3get%*. You
should understand why %3get%* works and %3getl%* is not required.
There are enough important new details in this %3eval-apply%* family
to warrant spending a bit of time. Most of the changes involve symbol table
operations. %3eval%* (and %3apply%*) no longer carry an explicit symbol table.
The property-list of tha atom contains the information now.
In this new scheme of things, %3get%* and %3getl%* search the symbol table
(p-list) for the appropriate bindings.
%3eval%* first checks if it has been given a number; any other atomic
expression given to %3eval%* is expected to be a variable and to
have a ⊗→%3VALUE%*-cell↔←.
If the %3car%* of the expression given to %3eval%* is atomic, then the
p-list of that atom is examined for one of three indicators.
We have already seen ⊗→%3EXPR%*↔← on {yon(P29)}, it is the indicator designating
a function represented as a λ-expression.
Evaluate the arguments and call %3apply%*. The indicator ⊗→%3FEXPR%*↔←,
designates a special
form. Pass the %2un%*evaluated argument list to %3apply%*.
The indicator, %3MACRO%*, is recognized on line %37%*.
There are actually two other indicators recognized by %3eval%*. ⊗→%3SUBR%*↔← is
the machine-language version of an %3EXPR%*; and ⊗→%3FSUBR%*↔← is the machine
version of a %3FEXPR%*.
.CENT(Problems)
I Evaluate the following using the new %3eval%*:
1. %3eval[((LAMBDA(L)(PRINT L))(QUOTE A))]%* assuming %3print%* is the usual printing function.
2. %3eval[(FOO(QUOTE A))]%* where %3foo <= λ[[l]print [l]].%1
3. %3eval[((CAR(QUOTE (FOO)))(QUOTE A))]%*, with %3foo%* as above.
4. %3eval[(FOO1(QUOTE A))]%* where %3foo1 <%4f%*= λ[[l]print[l]]%1.
and finally:
5. %3eval[((CAR (QUOTE FOO1)))(QUOTE A))].%1
Explain what happened. Can you "fix" it?
II Some implementations of LISP distinguish between %3FEXPR%*s and %3EXPR%*s
by modifying the prefix, %3LAMBDA%*. %3FEXPR%*s are stored with a prefix
%3NLAMBDA%*; %3EXPR%*s are stored with the normal %3LAMBDA%* prefix.
What are the advantages and drawbacks of this scheme?
III Recall the extensions to LISP-binding proposed in {yonss(P67)}. Discuss
their implementation in the light of the new %3eval%* and symbol table.
.SS(An alternative: deep bindings,deep binding)
There are some weaknesses in the shallow binding scheme espoused
in the previous sections. First, as we have seen ⊗→shallow binding↔← requires
that we be a bit careful in handling functional arguments.
Also there is an appreciable overhead in changing contexts.
Second, our strategy of requiring argument passing in a fixed number of
registers, AC%41%* through AC%4n%*, is unnecessarily restrictive. There
will be some arbitrary limit on the number of arguments which a function
may have. After a moment's reflection on the representation of the symbol table
as a stack {yon(P43)}, it should be apparent that we might try passing the
arguments to a function requiring %3n%* arguments as the first %3n%* elements
of a stack. The value returned by the function could be defined to be the
value located in the top of the stack. This holds promise. Consider the
evaluation of a form
.BEGIN CENTERIT;SELECT 3;
←f[g%41%*[ ... ]; ... g%4n%*[ ... ]] .
.END
The evaluation of the arguments is to proceed from left to right. If we perform
the procedure "calculate the argument; leave value in top of stack", then %3f%*
could expect to find values for its λ-variables as:
.BEGIN TABIT3(20,40,60);GROUP;
\value stack:\| value for %3x%4n%1\|
\\| value for %3x%4n-1%1\|
\\| ... ... \|
\\| value for %3x%41%1\|
.END
There will be no problem about searching to find the values; %3f%* "knows"
where to find the values in the stack. When %3f%* is finished its computation
it need only remove the top n elements from the value stack and add the value
which it computed.
This scheme seems to have the advantage of shallow binding: fast access
to values, but none of the disadvantages. It looks like the a-list scheme
for binding and unbinding. What's the problem? It's global variables.
If %3f%* wants to access a global variable how can it be found? All
we have stored on the stack is the %2value%* and there is no way that %3f%*
can "know" %2which%* value is the value of the global variable.
Surely we can solve this problem: simply store %2pairs%*##---##name-value pairs.
So what's the problem now? The expensive calculation only arises when we
access global variables. Most variables %2are%* local aren't they ---
or are they? Function names are variables and are almost always global;
%3car%* is a variable name, whose "value" is a primitive routine to
compute the %3car%* function. Seldom do you wish to redefine %3car%*.
Searching the stack for name-value pairs %2is%* more expensive than
picking up the value cell of the shallow binding scheme. We will soon see
that LISP compilers for deep binding %2can%* be made efficient
in their access of local and global variables; but the interpreter
%2will%* have to search. One of the worst cases will be the execution of a loop,
in which accesses to the same variables occur frequently.
This, perhaps is another good reason for removing control of iteration
from the hands of the programmer. The extent of (or even the presence of) a loop
which the user is
controlling by tests and goto's is difficult to discover. If a loop
is controlled by language constructs (WHILE, REPEAT, etc.) then the
interpreter might have some chance of improving the execution of the loop.
As we have previously said, deep binding is very reminiscent of the a-list
symbol table structure which was first a stack, then embellished to become
a tree when functional arguments appeared. But recall that the a-list scheme
had each name-value pair chained to its successor. Pointers into the table
structure (environment pointers) entered into this chain at various placees
to define an environment. With the a-list scheme, we were able to generate a
tree structure, but deep binding, so far, still has a stack-like structure.
Something must be done. Let's look at the a-list %3eval%* again.
First note that the environment pointers we generated for handling
functional arguments point into the symbol tables in very specific places;
they %2always%* point into the tables at the beginning of λ-bindings. They will
%2never%* point into the interior of a block of bindings. Thus each
%2block%* of λ-bindings can go onto a stack in a contiguous fashion.
Now recall the Weizenbaum environments: each environment has a local
symbol table (λ-variables, and %3prog%*-variables); each environment
also has entries for E%4a%* and E%4c%*. So we may simulate a tree on the
name-value stack if we include in each block of bindings, pointers
representing E%4c%* and E%4a%*. Thus the search strategy becomes yet a bit
more complex: when seeking a value for a variable run down the name-value
stack comparing names; when the block is exhausted we follow the E%4a%*-pointer.
To exit a block is easy and in fact much easier than the shallow binding
ritual: simply restore the E%4c%*-pointer.
***more,more***
.SS(Epilogue)
←%2Subtitled: But my Fortran program doesn't do all this crap!%1
It is quite true that a running Fortran, PL/1, or Algol program
is far less complicated as far as its symbol accessing mechanisms
are concerned. In Fortran there is a simple relationship between
variables and memory locations which will contain their values;
in Algol, there is a simple relationship between variables and positions
in the run-time stack.
In LISP, both the quality and the quantity of variables can change.
Arbitrary properties can be associated with atoms at run-time.
Indeed, the symbol table mechanism of LISP is more reminiscent of
that associated with the Fortran or Algol compiler. For these less
sophisticated languages it is the compiler which performs the mapping
from source language to running machine code. It is the compiler's
responsibility to discover the properties associated with each variable.
The compiler can do this because the semantics of the language is such
that at compile all (or almost all) properties of the variables are known.
This is not true for LISP. In general you cannot tell until run time what
the attributes of a particular atom are. The situation is really even worse
than this. Since programs and data are indistinguishable, we can %3cons%*-up a
list, assign it to a variable, then turn around and use that variable as
a function. Try that in Fortran.
Now the world isn't all this grim. There are LISP compilers (written
in LISP naturally). They can make many decisions at compile time
about the properties of variables, but in general the compiled code
will be interspersed with calls on %3eval%*. That is, %3eval%* will have to make
some decisions at runtime, because the compiler just doesn't know what to do.
This implies that compiled and interpreted code must be able to
communicate with each other. If a piece of compiled code calls a
λ-expression or conversely, the right thing must happen. The execution
of the program should be totally transparent as to whether any, or all, or
none of the functions are compiled. This means that the calling
sequences for both kinds of functions must be compatible. Less
obvious and by far more troublesome, is the communication of global
values between functions.
.END "JRA";